Расскажу про основные алгоритмы сортировки в программировании и приведу плюсы и минусы для каждого.
Привет! Меня зовут Дмитрий Курушкин.
Сегодня познакомимся с алгоритмом сортировки пузырьком, который существует в программировании. Посмотрим на теорию, и на практику на языке Python.
Сортировка пузырьком в Python
Данный вид сортировки заключается в сравнении соседних элементов.
Если правый элемент меньше, чем левый, то они меняются местами. В ином случае остаются на местах. Дальше берется вторая пара элементов, третья и так далее до конца. После того, как первый цикл обхода завершен, начинается следующий, до тех пор пока все элементы во всех парах не нужно будет переставлять.
Пример такой сортировки представлен на gif ниже.
Плюсы
- Достаточно простой в реализации и понимании
- Не требует дополнительной памяти (вся сортировка "на месте")
- Отлично подходит для небольших списков и частично неупорядоченных данных
Минусы
- Неэффективен для больших списков из-за квадратичной сложности (O(n^2)). Если список будет очень большим и максимально неупорядоченным, то я думаю прекрасно понятно насколько много времени потратится на упорядочивание.
Пример сортировки пузырьком в Python
Этот код сначала определяет функцию bubble_sort, которая принимает список arr для сортировки. Затем он выполняет внешний цикл, который проходит через все элементы списка. Внутри этого цикла есть еще один цикл, который сравнивает и обменивает соседние элементы. Если текущий элемент больше следующего, они меняются местами.
Процесс продолжается до тех пор, пока весь список не будет отсортирован. При этом используется флаг swapped, чтобы оптимизировать процесс и завершить сортировку, если на какой-то итерации не было обменов (то есть список уже отсортирован).
После вызова функции bubble_sort список my_list будет содержать отсортированные элементы, и они будут выведены на экран.
У меня есть Telegram канал. Там много фишек программирования и полезной информации.