Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [3, 1, 4, 2] → [1, 2, 3, 4]
.
Смысл пузырьковой сортировки заключается в следующем: мы начинаем с начала списка и сравниваем элементы попарно (нулевой и первый), если нулевой больше первого, то меняем их местами. Независимо от того, была ли замена или нет, мы шагаем вправо и сравниваем элементы вновь. Если на прошлом шаге была замена, то на этом шаге у нас окажется тот же элемент, и если он опять оказался больше, то «всплывет» снова вправо. Так за один проход наибольший элемент всплывет в самый-самый конец списка, подобно тому, как пузырек воздуха всплывает в бутылке воды. Когда все пузырьки всплывут – список будет отсортирован.
📎 Пример: a = [3, 1, 4, 2]
– 4 элемента:
Первый проход:
- Сравним
a[0] = 3
иa[1] = 1, 3 > 1
. Меняем их местами. Теперьa = [1, 3, 4, 2]
. - Сравним
a[1] = 3
иa[2] = 4, 3 < 4
. Менять не надо. - Сравним
a[2] = 4
иa[3] = 2, 4 > 2
. Меняем.a = [1, 3, 2, 4]
.
Проход окончен. 4 «всплыла» в самый конец списка на свое место a[3]
. Поэтому мы не трогаем больше конец списка, но список еще не отсортирован до конца, и следующий проход будет рассматривать только первые 3 элемента списка.
Второй проход:
- Сравним
a[0] = 1
иa[1] = 3, 1 < 3
. Менять не надо. - Сравним
a[1] = 3
иa[2] = 2, 3 > 2
. Меняем их.a = [1, 2, 3, 4]
. Проход окончен.
Третий проход:
- Сравним
a[0] = 1
иa[1] = 3, 1 < 3
. Менять не надо. Список отсортирован. Можно выходить.
👨💻 Переходим к реализации на Python:
def bubble_sort(a): n = len(a) # номер прохода i = 0..(n-2), т.е. (n-1 раз): for i in range(n - 1): # номер сравнения j = 0..(n - i - 2) for j in range(n - i - 1): # сравниваем только соседние элементы if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j]
Алгоритм прост, но можно запутаться в индексах: с какого элемента и куда бежать, что с чем сравнивать. Как лучше запомнить:
- Начинаем всегда с начала (0-го элемента).
- Число проходов меньше на 1, чем число элементов
- С каждым проходом мы делаем все меньше и меньше сравнений, так как сортированный хвост списка растет на 1 после каждого прохода
- Сравниваем только соседние элементы
a[j] > a[j + 1]
, (а не i и j). - Если знак сравнения перевернуть, то сортировка будет по убыванию.
Временная сложность алгоритма квадратичная O(n^2) – имеются два вложенных цикла по элементам. Поэтому алгоритм медлителен для больших списков. В реальной жизни чаще применяются другие алгоритмы сортировки, но пузырек до сих пор не забывают преподавать и спрашивать.

🐉 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈