Bubble Sort. Один из самых простых алгоритмов сортировки элементов в массиве. С него начинается изучение алгоритмов вообще.

Алгоритм обходит массив, сравнивает попарно соседние элементы, и меняет их местами, если они стоят в неправильном порядке. Обход повторяется, пока не окажется что все пары стоят правильно.

Сортировка называется пузырьковой, потому что в процессе обхода большие элементы поднимаются «со дна» (с начала массива) «наверх» (в конец), как бы проталкиваясь мимо каждого следующего элемента-соседа, как пузырек воздуха в воде.

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

Алгоритм не требует дополнительной памяти.