Продолжаем наше изучение алгоритмов и сегодня начнем разбирать пузырьковой сортировки, один из наиболее наглядных методов упорядочивания данных. Идея сортировки в целом подобна приведению в порядок перепутанной колоды карт, когда требуется расположить элементы от меньшего к большему или наоборот. В программировании эта задача возникает постоянно: будь то числа, строки или другие данные, требующие определённой последовательности. Например, изначальный список
[64, 34, 25, 12, 22] после сортировки превращается в [12, 22, 25, 34, 64].Название "пузырьковая" отражает суть процесса: более лёгкие элементы, подобно пузырькам воздуха в воде, постепенно всплывают к началу списка, в то время как тяжёлые опускаются в конец. Алгоритм построен на простом принципе: последовательно сравниваются соседние элементы, и если они расположены в неправильном порядке, происходит их обмен. Эти действия повторяются до тех пор, пока весь массив не будет упорядочен.
Для лучшего понимания разберём визуальный пример сортировки списка
[5, 3, 8, 4, 2] по возрастанию. В первом проходе сравниваются 5 и 3 — поскольку 5 больше 3, они меняются местами, и список становится [3, 5, 8, 4, 2]. Далее 5 и 8 остаются на своих местах, так как 5 меньше 8. Затем 8 и 4 обмениваются, получается [3, 5, 4, 8, 2]. Наконец, 8 и 2 также меняются, и результат первого прохода — [3, 5, 4, 2, 8]. Обратите внимание, что самое большое число 8 оказалось в конце, заняв свою окончательную позицию. Второй проход перемещает 5 на предпоследнее место: после сравнений и обменов список принимает вид [3, 4, 2, 5, 8]. Третий проход ставит на место 4: [3, 2, 4, 5, 8]. Четвёртый проход завершает сортировку, обменяв 3 и 2, и итоговый результат — [2, 3, 4, 5, 8].Теперь перейдём к программной реализации. Код функции пузырьковой сортировки на Python выглядит следующим образом:
def bubble_sort(arr):
"""Пузырьковая сортировка списка."""
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
Разберём каждую часть. Функция
bubble_sort принимает список arr. Переменная n хранит его длину. Внешний цикл for i in range(n) определяет количество полных проходов по списку. Внутри него устанавливается флаг swapped = False, который отслеживает, были ли совершены обмены во время текущего прохода. Это важная оптимизация: если обменов не произошло, список уже отсортирован, и дальнейшие проходы не нужны.Внутренний цикл
for j in range(0, n - i - 1) отвечает за попарное сравнение соседних элементов. Выражение n - i - 1 ограничивает диапазон, потому что после каждого прохода самый крупный элемент "всплывает" в конец, и проверять его уже не требуется. Например, для списка из пяти элементов при первом проходе (i = 0) будут сравниваться пары с индексами от 0 до 3, при втором (i = 1) — от 0 до 2, и так далее.Внутри внутреннего цикла условие
if arr[j] > arr[j + 1]: проверяет, стоит ли текущий элемент правее, чем следующий. Если да, то с помощью конструкции arr[j], arr[j + 1] = arr[j + 1], arr[j] элементы меняются местами, а флаг swapped устанавливается в True. После завершения внутреннего цикла проверяется значение флага: если он остался False, что означает отсутствие обменов, внешний цикл прерывается оператором break. В конце функция возвращает отсортированный список.Для демонстрации работы приведём полный пример: