Алгоритм сортировки пузырьком, или BubbleSort, является одним из самых простых и интуитивно понятных способов упорядочивания данных. Несмотря на свою простоту, он позволяет лучше понять основы алгоритмического мышления и принципы работы более сложных алгоритмов.
Что такое BubbleSort?
Алгоритм сортировки пузырьком применяется к неупорядоченным массивам элементов, будь то числа, строки или объекты. Основная идея состоит в последовательном сравнении пар соседних элементов с последующим их обменом, если они стоят в неверном порядке. Этот процесс продолжается до тех пор, пока массив не будет полностью отсортирован.
Алгоритм сортировки пузырьком (BubbleSort) может сравнивать так же строки и объекты.
Почему "пузырёк"?
Название "пузырёк" возникает из-за аналогии с движением пузырьков воздуха в воде: большие элементы "всплывают" к концу массива. Представьте себе, что вы начинаете с массива чисел. На каждом проходе по массиву самые крупные элементы постепенно перемещаются ближе к "поверхности" — в правую часть массива, в то время как меньшие остаются слева.
Алгоритм сортировки пузырьком (BubbleSort) повторяется циклично и несколько раз, проходя от первой до последней итерации, пока не закончится сравнительная аналитика между цифрами и они не отсортируются в зависимости от величины числа, размещая меньшие цифры слева, а большие числа справа.
В результате мы проходим массив n количество раз и каждый раз сравниваем 2 числа. И это приводит к всплытию наверх больших чисел по сравнению с маленькими.
В результате получается отсортированный массив.
Пошаговый разбор работы алгоритма
Рассмотрим исходный набор чисел: [5, 3, 8, 4, 2].
- Начнем сравнение с первых двух элементов: (5, 3). Поскольку 5 > 3, меняем их местами.
- Сравниваем следующую пару: (5, 8). Никаких изменений, продолжаем.
- Сравниваем (8, 4). Меняем их, список теперь [3, 5, 4, 8, 2].
- Сравниваем последние: (8, 2). Меняем их, получая [3, 5, 4, 2, 8].
Первые четыре элемента теперь снова проходят через этот процесс. И так продолжается, пока данные не упорядочатся окончательно.
Детальный код с пояснениями в Python
Тот же код ниже для копирования и вставки в программу. Не забывайте про необходимый отступ пробелами в определённых местах в начале строки, так как код на сервере блога может отображаться некорректно.
def bubble_sort(arr): # Определяем функцию, принимающую список arr
n = len(arr) # n определяет длину списка arr
for i in range(n): # Внешний цикл проходит по всем элементам списка
for j in range(0, n-i-1): # Внутренний цикл проходит по необработанной части списка
if arr[j] > arr[j+1]: # Сравниваем arr[j] и arr[j+1]
arr[j], arr[j+1] = arr[j+1], arr[j] # Меняем элементы местами, если стоят неправильно
# Пример использования:
sample_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(sample_list)
print("Отсортированный массив:", sample_list)
Результат работы кода:
Рекомендации по улучшению кода
Для улучшения пузырьковой сортировки можно вводить "флаг" вопросов, который прекращает работу, если на проходе по массиву не было ни одного обмена, что означает завершение сортировки. Это улучшение сокращает количество ненужных проходов и тем самым повышает производительность.
Это изменение улучшает алгоритм без значительного усложнения кода.
Временная сложность
К сожалению, базовая версия алгоритма имеет временную сложность O(n²) в худшем и среднем случае, так как каждая пара элементов может быть сравнима за один проход. Однако, для небольших наборов данных или уже почти упорядоченных массивов данный метод может выступать очень эффективно.
Заключение
Алгоритм сортировки пузырьком, при всей его простоте, иллюстрирует силу базовых методов сортировки и проблемы неэффективности. Хотя BubbleSort редко используется в коммерческих приложениях из-за своей медлительности, он остается отличным вводным шагом в мир алгоритмов и структур данных. Понимание и проработка таких базовых алгоритмов является необходимым этапом подготовки для работы с более сложными и оптимизированными сортировочными методами.
Полезные ресурсы:
Сообщество дизайнеров в VK
https://vk.com/grafantonkozlov
Телеграмм канал сообщества
https://t.me/grafantonkozlov
Архив эксклюзивного контента
https://boosty.to/antonkzv
Канал на Дзен
https://dzen.ru/grafantonkozlov
---------------------------------------
Бесплатный Хостинг и доменное имя
https://tilda.cc/?r=4159746
Мощная и надежная нейронная сеть Gerwin AI
https://t.me/GerwinPromoBot?start=referrer_3CKSERJX
GPTs — плагины и ассистенты для ChatGPT на русском языке
https://gptunnel.ru/?ref=Anton
---------------------------------------
Донат для автора блога
