Алгоритм обходит массив, сравнивает попарно соседние элементы, и меняет их местами, если они стоят в неправильном порядке. Обход повторяется, пока не окажется что все пары стоят правильно.
Сортировка называется пузырьковой, потому что в процессе обхода большие элементы поднимаются «со дна» (с начала массива) «наверх» (в конец), как бы проталкиваясь мимо каждого следующего элемента-соседа, как пузырек воздуха в воде.
В худшем случае самый маленький элемент опускается с самого верха. Ему нужно пройти мимо всех n элементов. Значит алгоритм совершит n обходов, каждый раз сравнивая все n-1 пар. Отсюда сложность алгоритма по времени
O(n^2). В лучшем же случае массив уже отсортирован, это выясняется за один проход (n-1 операций сравнения) – O(n).Алгоритм не требует дополнительной памяти. Такая разновидность сортировок называется сортировкой на месте (in-place sorting).