Быстрая сортировка пузырьком – это реальноКаждый уважающий себя программист не только знает, что такое сортировка, но и способен быстро написать какую-нибудь из них, чаще всего quicksort или слиянием. Но сегодня я расскажу вам о быстрых вариантах сортировки обменами или же, как ее называют, сортировки пузырьком.

Самый стандартный вариант сортировки пузырьком – глупая сортировка. Массив просматривается слева направо, и сравниваются элементы-соседи. Найден непорядок – меняются местами и все начинается сначала. Время работы в среднем O(N3), что очень долго, но чего еще ожидать от сортировки под названием «глупая»?

Но стоит чуть-чуть подкорректировать алгоритм и мы получим сортировку с временем O(N2), и это будет уже стандартная пузырьковая сортировка. Достаточно просто не начинать сначала после обмена, а продолжать. Она всё также неэффективно работает, но работает же.

Еще одна коррекция и мы получаем коктейльную сортировку. После «выдавливания» максимума в конец массива (то есть первый проход по массиву), мы начинаем проход в обратную сторону и перемещаем в самое начало минимум. Доказано, что коктейльная сортировка работает чуть быстрее, чем оригинальная пузырьковая (и намного быстрее при самом худшем случае – из массива, отсортированного по убыванию получить массив, отсортированный по возрастанию).

Для дальнейшего убыстрения сортировки мы вернемся к проходам по массиву в одну сторону и немного изменим шаг прохода. Если до этого мы двигались элемент за элементом, то сейчас будем немножко прыгать. Сортировка называется чётно-нечётная. Используются в ней два прохода: чёт-нечёт (элементы, находящиеся на четных местах сравниваются с соседями на нечетных) и, сразу после него, нечёт-чёт (аналогично, только наоборот). Если в обычной пузырьковой сортировке в первый проход мы сдвигаем максимум в конец, то тут мы ближе к концу сдвигаем все крупные элементы. Сортировка заканчивается, когда не было произведено ни одного обмена за два прохода подряд. Точное время не установлено, но в среднем получается быстрее, чем пузырек.

И последняя, самая быстрая сортировка обменами – сортировка расчёской. Тут идея состоит в том, чтобы сравнивать не соседние элементы, а элементы с некоторым шагом. Самый оптимальный шаг доказан математически: при первом проходе размер массива делится на «фактор уменьшения», равный 1.247, при втором проходе получившееся число снова делится на фактор уменьшения (естественно, полученный результат каждый раз округляется до ближайшего целого). Так происходит до того момента, пока шаг не становится равным единице, и дальше массив отсортировывается обычным пузырьком. Время работы - O(N4/3).

Вот собственно и все самые интересные факты про самую простую сортировку.

  
Электронная книга: как правильно выбрать?
В настоящее время, электронные книги среди многих пользователей становятся всё более и более популяр
Какой правильно выбирать планшетный ПК?
Подобрать планшетный ПК достаточно непросто. Сегодня присутствует множество предложений, среди котор
Влияние музыки на человека трудно переоценить
Лечите душу ощущениями и…музыкой. Влияние музыки на человека поистине значительное, и это факт, о

Оставить комментарий