Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Вариации алгоритма пузырьковой сортировки
Данная статья является только первой в серии статей об алгоритмах сортировок, которых несть числа. Ну, а пузырьковая сортировка (сортировка пузырьком) сама известная и одна из самых алгоритмически простых.
Действительно, не все алгоритмы сортировок легко понять. А пузырьковую понять легко.
Пусть дан массив чисел
4 2 1 3
Выполним в цикле следующие действия: на каждом шаге цикла от 0 до 2 будем сравнивать соседние элементы (i-й и i+1-й). Если i-й больше i+1-ого то меняем их местами. Для данного случая легко получим
2 1 3 4
Самый большой элемент оказался в конце. Это и есть пузырёк, который "всплыл".
Легко видеть, что если провести ещё одну подобную процедуру уже над результатом, то получим
1 2 3 4
Т.е. мы упорядочили массив по возрастанию. Конечно, подобным образом можно упорядочить и по убывании.
У нас сортировка вышла в два прохода, но в общем случае проходов может понадобиться N, где N - длина массива. Получается, что в общем случае время сортировки будет зависеть от N*N.
Ниже, на языке Python представлена простая программа пузырьковой сортировки.
Представленный выше алгоритм является базовым. Его можно развить и улучшить, чем мы сейчас и займёмся.
Внутренний цикл от 0 до N-1. Но ведь после первого прохода на последнем месте уже оказывается максимальный элемент. Значит второй проход следует делать до N-2. И т.д.
Вот результат
Еще одно усовершенствование алгоритма связано с тем, что мы никак не проверяем тот факт, что может быть массив уже упорядочен и дальше сортировку проводить не нужно.
Вот так это можно реализовать
Переменная flag показывает тот случай, когда не было ни одной перестановке, а, следовательно, сортировка закончена.
Замечание
Обычно в учебниках пишут, что пузырьковая сортировка самая медленная. На самом деле всё гораздо сложнее. Нужно тогда дать определение того, как сравнивать сортировки. На время выполнения сортировки влияют: длина массива, исходное состояние (упорядочен, не упорядочен, частично упорядочен и каковы длины упорядоченных фрагментов, упорядочен в обратном порядке). Конечно, нужно сравнивать сортировке в конкретной реализации, беря за основу какие-то интегральные показатели.
Ну вот пока всё. Ну а дальше будут статьи о других сортировках. На нашем канале будет много ещё всего интересного.
Следующая статья по сортировкам...
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.