Зарождение компьютеров, активное развитие точных наук, появление дисциплин на стыке направлений потребовали выработать принципы работы с данными, в том числе способы упорядочивания. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают один из базовых методов группировки, построенный на попарном сравнении.
В 1956 году американский математик Эдвард Гарри Френд впервые упоминает способ сортировки массива данных методом обмена в работе под названием «Sorting on electronic computer systems». Через шесть лет канадский учёный Кеннет Айверсон, автор языка программирования APL, использует термин bubble sort (сортировка пузырьком).
Название bubble sort дано по аналогии: при каждом проходе программы наибольшие значения массива всплывают на поверхность, словно пузырьки воздуха в воде. Но поочерёдный подъём увеличивает количество итераций.
Метод разбора данных считается самым простым среди собратьев. Идея – последовательно сравнивать пары элементов, пока не выполнится условие: массив упорядочен по возрастанию или убыванию.
Рассмотрим на примере. Дан массив из шести составляющих [38, 3, 31, 59, 17, 85]. Необходимо провести сортировку по возрастанию.
Возьмём первую пару элементов на позициях 0 и 1. Меньшее значение 3 стоит после 38, поэтому меняем числа местами и переходим дальше.
Так как алгоритм последовательно сравнивает пары, вновь оцениваем элемент на позиции 1. Теперь тут находится число 38 – при сопоставлении с 31 видим: дуэт тоже требует перестановки.
Далее взгляд падает на сочетание 38 и 59. Числа уже расположены в требуемой последовательности, значит, ничего делать не нужно.
В паре 59 и 17 переставляем значения: 17 уходит на позицию 3.
Заключительное дуо вновь располагается в запрашиваемом порядке – не трогаем.
В полученном массиве не все элементы находятся на местах, поэтому алгоритм возвращается к позиции 0. Пары 0–1 и 1–2 соответствуют последовательному увеличению. В 2–3 снова меняем положения.
После корректировки дуэта 2–3 алгоритм оценивает пару 3–4, а 4–5 уже не смотрит: на предыдущем шаге зафиксировано, что крайние числа финальны.
Но число 17 всё ещё не на месте, поэтому программа вновь пробегает 0-1 и на паре 1-2 выполняет заключительный обмен. Затем следует проверка 2-3: убедившись в верном расположении, алгоритм завершает работу.
Таким образом, сортировка по возрастанию преобразовала массив из шести элементов [38, 3, 31, 59, 17, 85] в [3, 17, 31, 38, 59, 85]. Задача решена.
Скорость метода имеет квадратичную зависимость:
T = O(n2),
где T – время работы, n – число элементов.
Метод работает с исходным массивом на месте и в моменте, поэтому нужна одна постоянная ячейка памяти для временного хранения при перестановке:
Q = O(1),
где Q – требуемый объём.
Алгоритм прекрасно годится для обучения сортировкам и демонстрации принципа работы. Применим для быстрой оценки упорядоченности короткого списка или финального прохода. За время существования получил несколько модификаций: чёт-нечёт, расчёска и перемешивание.