Пузырьковая фильтрация — это алгоритм сортировки массива, который применяется для массивов небольших объёмов.
Наиболее быстрым способом сортировки массивов считается быстрая сортировка. Но были разработаны и иные методы, такие как, сортировка выбором, вставками, слиянием, распределением. Были изобретены и гибридные и параллельные сортировки. Но самым простым способом сортировки считается пузырьковая фильтрация и различные её модификации.
Пузырьковая фильтрация
Метод сортировки обменами, к которому относится и пузырьковая фильтрация, основан на упорядочивании элементов массива. Упорядочивание является итогом последовательного пересмотра массива, при котором сравниваются между собой пары компонентов. В случае, когда эта пара компонентов не отсортирована по отношению друг к другу, то они меняются местами. Отличие разных модификаций сортировки, основанных на обмене, состоит в выборе варианта обхода элементов массива и выборе подходящей пары, которую надо сравнивать. Одной из версий является, так называемая, глупая сортировка. Суть её состоит в просмотре массива в направлении слева направо и сравнении соседних элементов. При обнаружении пары компонентов, которые ещё не проходили сортировку, они меняются местами и процесс начинается с начала. Эта процедура продолжается до тех пор, пока не останется неотсортированных элементов.
Если сделать небольшую модификацию, а именно после смены мест найденной неотсортированной пары элементов не возвращаться в начало алгоритма, а продолжать обход массива дальше, то получим алгоритм пузырьковой сортировки (фильтрации). То есть это сортировка путём выполнения простых обменов со следующим принципом действия:
- Выполняется обход массива с самого начала до конца. При этом меняются местами не проходившие сортировку соседние компоненты. По итогам первого обхода последним окажется самый большой элемент.
- Выполняется повторный обход массива начиная с первого элемента и заканчивая предпоследним. Во время прохода так же меняются местами неотсортированные пары. Предпоследним будет следующий по размерам компонент.
- Процесс продолжается до завершения сортировки массива.
Если ещё немного модифицировать метод, а именно не только перемещать максимальные компоненты в конец массива, но и отсылать к началу минимальные элементы, то получится шейкерная сортировка. Другое её название сортировка перемешиванием или коктейльная. То есть здесь вначале, как и в пузырьковой сортировке, максимальные значения отправляются в конец, но затем, по достижении конца массива, выполняется разворот и идёт обход в обратную сторону. При этом обходе в начало отсылаются самые маленькие компоненты. Процесс продолжается до достижения при очередном проходе середины массива. Этот вид сортировки работает быстрее чем пузырьковый метод, так как проход ведётся в обоих направлениях.
Чётно-нечётная сортировка
Если вернуться снова просто к обходу слева направо, но с более широким шагом, то получится чётно-нечётный тип сортировки. На начальном обходе компоненты с нечётными номерами сравниваются с соседними элементами, имеющими чётные номера и если нужно, делается обмен. То есть первый номер сравнивается со вторым, далее третий с четвёртым, пятый с шестым и далее в том же порядке. Далее процесс выполняется наоборот, чётные номера элементов сравниваются (меняются местами) с нечётными номерами и так далее. Работа алгоритма прекращается, если по завершении двух обходов к ряду, не выполнено ни одного обменного действия. На этом сортировка закончена. В стандартном способе пузырьковой сортировки при каждом обходе происходит планомерное выдавливание максимального на данный проход значения в окончание массива. При использовании же чётных и нечётных проходов, получается смещение всех больших компонентов единовременно за один обход в правую сторону на один элемент. В итоге процесс выполняется быстрее.
Ещё в 1980-ом году Влодзимеж Добосиевич обосновал медленную работу пузырьковой сортировки и её модификаций. Он назвал маленькие по величине компоненты, находящиеся в конце массива, черепашками. Пузырьковые способы сортировки имеют ориентацию на большие компоненты массивов, которые довольно быстро передвигаются. А маленькие элементы перемещаются медленно. Увеличить скорость их перемещения возможно при помощи метода сортировки, названного расчёской.
Метод сортировки "расчёска"
В приведённых выше методах сортировки при обходе массивов идёт сравнение соседних компонентов. В сортировке способом расчёски изначально выбираются довольно большие дистанции между парами элементов, выбранных для сравнения и затем в процессе сортировки массива эта дистанция сокращается до минимума. То есть, образно говоря, выполняется причёсывание массива, которое осуществляет разглаживание «волос на красивые пряди». Изначальная дистанция между парой компонентов, подлежащих сравнению, должна выбираться исходя из учёта специального коэффициента, который называется уменьшительным фактором. Его оптимальная величина приблизительно равняется 1,247. Первоначально, дистанция между парой компонентов равняется объёму массива, поделённого на величину уменьшительного фактора. Результат деления необходимо округлить до целого значения. Далее, после обхода массива с найденным шагом, опять выполняется деление шага на уменьшительный фактор. Затем делается обход массива с вновь полученным значением шага. Процесс продолжается до тех пор, пока разность индексов не станет равной единице. И далее выполняется уже сортировка пузырьковым методом.
Теория и практика помогли выявить оптимальную величину уменьшительного фактора:
Рисунок 1. Уменьшительный фактор. Автор24 — интернет-биржа студенческих работ
Этот способ был обнародован примерно в середине семидесятых годов прошлого века, но тогда он не был оценен по достоинству. И лишь когда написание программ перестало быть привилегией отдельных специалистов и научных работников, а стало массовым явлением, этот метод получил второе рождение.
