Пузырьковая сортировка в excel

Обновлено: 05.01.2025

В статье разберем 9 видов сортировок, рассмотрим суть этих алгоритмов. Скорости, сложность алгоритмов и практическое их применение оставим за скобками. Задача статьи показать, что одну и туже задачу можно решать различными способами, показать практическое применение языка VBA и помочь начинающим в его освоении.

Подготовительный этап

Перед тем как начинать писать алгоритмы немного подготовимся. Создадим общую константу n для хранения размера массивов. Вставим на лист диаграмму, чтобы отслеживать как все работает. В коде объявим объект нашей диаграммы, на которой будем просматривать ход процесса сортировки. Чтобы не дублировать код в каждом алгоритме сортировки мы будем использовать процедуру инициализации Init().

Чтобы наша диаграмма с результатом не подвисала и обновлялась напишем такую функцию.

В качестве массивов будем использовать диапазон ячеек A1:Y1. Напишем еще одну коротенькую процедуру для перемешивания этого массива, точнее заполнения его числами от 1 до 25 в случайном порядке.

Теперь все готово, давайте писать алгоритмы сортировки.

Сортировка пузырьком

Пузырьковая сортировка (или сортировка простыми обменами) пожалуй самый неэффективный алгоритм сортировки и в тоже время пожалуй самый известный.

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

Вот код сортировки данным алгоритмом на VBA. Еще стоит обратить внимание на переменную Flag она служит индикатором того, что массив досрочно отсортирован и можно заранее выйти из цикла и сократить вычислительные ресурсы.

Далее описана процедура Swap для перестановки ячеек местами. После перестановки ячеек вызывается процедура ChartRefresh обновления диаграммы.

Сортировка перемешиванием

Этот алгоритм является разновидностью пузырьковой сортировки. Также этот алгоритм называют Шейкерной сортировкой или двунаправленной. Основное отличие от обычной сортировки пузырьком в том, что массив сначала просматривается слева направо и максимальный элемент перемещается вправа, а после мы проходим по массиву справа налево (от последнего отсортированного элемента) и наименьший элемент перемещается влево. Вот на графике отчетливо это видно.

Алгоритм немного больше, но по сложности аналогичный, вот его код на VBA.

Сортировка выбором

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

Объединение сортировки пузырьком и сортировки выбором

Можно ускорить алгоритм сортировки пузырьком объединив его с алгоритмом сортировки выбором. Для этого нужно определять минимальный элемент во внутреннем цикле и после каждого прохода по списку обменивать найденный минимальный элемент с первым неотсортированным слева. Таким образом, мы сокращаем в 2 раза число перестановок, но при этом увеличиваем в 2 раза число сравнений.

Код отличается только 2 строчками:

Сортировка вставками

Вот определение сортировки с википедии

Это алгоритм, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Другими словами мы во внешнем цикле проходим по всем элементам массива, а во внутреннем цикле сравниваем правый элемент с уже отсортированными элементами слева и перемещаем его при необходимости. Вот как это выглядит визуально:

Код тоже думаю окажется для вас достаточно простым.

Гномья сортировка

Визуально отличия от сортировки вставками нет, однако в код совершенно другой так как нет никаких вложенных циклов. Алгоритм в цикле проходит по всем элементам, сравнивая текущий элемент с предыдущим. Если элементы стоят верно переходит к следующему, если нет, меняет их местами и переходит к предыдущему элементу.

Сортировка слиянием

Простые алгоритмы сортировки мы разобрали, теперь давайте рассмотрим более сложные виды сортировок. Хотя главное понять суть алгоритма и его реализация уже не будет казаться сложной.

Суть алгоритма сортировки слиянием состоит в том, чтобы разбить исходный массив на более мелкие массивы, отсортировать каждый по отдельности, а после объединить результаты.

Для этого первоначальный массив разбивается на 2 части пополам (ну или почти пополам если количество нечетное), каждая половинка разбивается еще пополам и так до тех пор, пока мы не получим массивы состоящие из 1 элемента. После прохождения процедуры разбивки на части, слияние каждой части и ее сортировка. Например, массив содержит числа 5 2 1 3 4. Разбиваем его на две части: 5,2,1 и 3,4 . Первую часть 5,2,1 разбиваем еще на две части 5,2 и 1. Далее 5,2 еще на две части 5 и 2. А теперь идем обратно, сортируем и сливаем массивы. Получается 2,5 и 1, объединим дальше - 1,2,5 , последняя итерация отсортирует исходный массив 1 2 3 4 5. При слиянии учитывается тот факт, что массивы уже отсортированы по отдельности, поэтому объединение проходит быстрее.

Вот визуализация работы алгоритма:

Код состоит из двух частей. Первая MergeSort - рекурсивная функция разделения массивов, т.е. эта функция запускает саму себя. Это происходит до тех пор, пока размер массива больше 1, иначе запускается функция MergeSort для каждой из частей.

После того как массивы разобьются запускается функция Merge(left, right), которая сортирует и объединяет массив обратно.

В качестве сортировки и объединения можно использовать различные алгоритмы, например такой. Если кто-то предложит более изящное решение - пишите в комментариях.

Так как функция у нас рекурсивная, то первый ее запуск необходимо сделать из отдельной процедуры, вот так:

Быстрая сортировка

Алгоритм быстрой сортировки - один из самых быстрых и эффективных и часто используется в практике. При этом он достаточно простой.

Суть алгоритма в следующем:

Выбрать из массива опорный элемент. Например, взять элемент в середине массива (в целом это может быть любой из элементов).
Сравнить остальные элементы массива с выбранным опорным элементов и разбить массив на 2 части:
- элементы, которые меньше или равны опорному элементу;
- элементы, которые больше опорного.
Далее пункты 1 и 2 повторяются рекурсивно для каждой части массива, до тех пор пока размер части состоит из более чем 1 элемента.

На визуализации к сожалению что-то разглядеть сложно. Алгоритм достаточно быстро отрабатывает:

Вот код данного алгоритма на VBA.

Запуск рекурсивной функции быстрой сортировки запустим из отдельного метода.

Пирамидальная сортировка

Пирамидальная сортировка или как еще ее называют "Сортировка кучей" использует в своем алгоритме двоичное дерево.

Это такое дерево, для которого выполнены следующие условия:

Значение в любой вершине не меньше, чем значения её потомков.
Длина веток дерева не отличается друг от друга более чем на 1 слой.
Последний слой заполняется слева направо без «дырок».

Вот пример дерева, которое можно найти на википедии:

Это дерево можно представить в виде следующего массива, где для любого элемента A[i] потомками являются элементы A[2i] и A[2i+1].

Т.е. для каждого элемента кучи справедливы следующие условия: A[i] >= A[2i] и A[i] >= A[2i+1].

Алгоритм пирамидальной сортировки состоит из следующих шагов:

Построение массива в виде двоичного дерева.
Исключение корня дерева (максимального значения массива) из массива и перенос его в конец последовательности.
После исключения корня дерево перестраивается и его корень опять отсекается и переносится в конец.
Так происходит до тех пор, пока вся последовательность не отсортируется.

Вот визуальное отображение выполнения этого алгоритма:

Ниже код пирамидальной сортировки на VBA. Который формирует двоичную кучу и корень этой кучи переносит в конец последовательности. Так происходит n раз.

Рис.1 Алгоритмы сортировки массивов.VBA.Макросы.

В моем массиве хранятся (генерируются случайным образом) только целые числа.
Массив глобальный, т.е. все подпрограммы имеют к нему доступ.

Public a( ) As Integer

Поскольку сортировка массива подразумевает замену элементов местами, то без процедуры (подпрограммы) swap здесь не обойтись.
Нет, обойтись, конечно, можно, но придется часто повторять однотипный код из трех операторов.

Итак, замена значений переменных с использованием третьей (временной):

Private Sub swap(p As Integer, q As Integer, bool As Boolean)
'меняет местами два элемента массива
Dim t As Integer
t = a(p): a(p) = a(q): a(q) = t
bool = False
End Sub

В процедуру передаются два индекса элементов массива и логическая переменная (по ссылке), которую я буду называть «показатель сортировки» или «флаг сортировки».
При любом вызове этой процедуры, как видите, флаг сбрасывается.

Метод Пузырька или пузырьковая сортировка

наиболее простой и не очень быстрый метод. Есть смысл использовать его для небольших массивов и в учебных целях.

Его суть: сравнить два соседних элемента массива и если они расположены не в «нужном» порядке, то поменять их местами.

Вот условие сортировки по возрастанию:
If a(i) > a(i + 1) Then swap i, i + 1, bool

А вот по убыванию:
If a(i) < a(i + 1) Then swap i, i + 1, bool

Показал и все. В дальнейшем сортирую только по возрастанию. Для удобства восприятия
Как видите, если соседние элементы равны или не удовлетворяют условию замены, то просто ничего не происходит, а элементы остаются на своих местах.

Следующий момент: соседние элементы, конечно, рассматриваются и сравниваются парами в цикле. Но можно цикл начать от начала массива (прямой прогон), а можно с конца (обратный прогон).

Вот, прямой прогон:
For i = 1 To sizeArr -1 'прямой ход.
If a(i) > a(i + 1) Then swap i, i + 1, bool
Next i

А вот, обратный прогон:
For i = sizeArr To 2 Step -1 'обратный ход.
If a(i) < a(i - 1) Then swap i, i - 1, bool
Next i

Конечно, за один прогон, массив будет отсортирован только в очень редких случаях, и данный метод подразумевает неопределенное (необходимое и достаточное) количество прогонов для достижения желаемого результата Но поговорим о прямом и обратном прогонах. В чем их отличие? И почему метод называется «методом пузырька»?

При прямом прогоне слева направо устремляются более крупные числа, как пузырьки воздуха всегда устремляются вверх. Если на первом месте было максимальное число данного массива а(1)=max, то при прямом прогоне оно беспрепятственно на каждом очередном шаге займет второе, третье и наконец последнее, самое правое место в массиве a(sizeArr)=max.
Если же это было не самое большое число (но и не самое маленькое), то оно тоже устремится направо, пока не встретит на своем пути более крупное число. Дальше путь к вершине продолжит уже это новое более крупное число.
Вспомните, как большие пузырьки всегда всплывают быстрее

Таким образом, за один прямой прогон массив отсортирован не будет, но его последним элементом станет обязательно максимальное по величине число. При этом первым элементом массива станет наименьшее из чисел, располагавшихся на первом и втором местах.

А при единственном обратном прогоне (не забывайте, что массив сортируется по возрастанию) первым элементом массива станет минимальное число. Про остальные ничего определенного сказать нельзя, кроме того, что каждое более мелкое число по сравнению со своим левым соседом, обменялось с ним местами.
За второй обратный прогон, вторым элементом станет второе по «мелкости» число. Оно никак не сможет занять первое место, так как там уже находится минимальное в массиве число. Поэтому сделаем однозначный вывод, что каждый последующий прогон целесообразно заканчивать на шаг раньше предыдущего. Этим сэкономим немного машинного времени.

Так сколько же раз нужно выполнить прогоны, чтобы массив полностью был отсортирован?

Конечно, для полной уверенности и 100% гарантии можно любой из прогонов (это без разницы) выполнить sizeArr-1 раз.
К гадалке не ходи, все элементы будут расположены по возрастанию. Но при этом вполне вероятно, что последние прогоны проходили бы уже без замен элементов, так как последние элементы были расположены по порядку и условие на замену не выполнялось. Вот, чтобы исключить, подобное и сэкономить еще немного машинного времени, используют «флаг сортировки», т.е. обычную логическую переменную, которая до начала прогона имела бы значение true. Даже при единственной замене двух «соседей» за весь прогон, в процедуре swap данный флаг сбросится. Но зато уж, если после прогона флаг остался равным true, то можно с уверенностью прекращать сортировку, т.к. из всех пар соседних элементов, ни одна не выразила желание поменяться местами. Это та же самая 100% гарантия, что и при избыточности прогонов.

Private Sub prForward(p As Integer, q As Integer, bool As Boolean)
Dim i As Integer
bool = True
For i = p To q 'прямой ход. максимальный элемент займет самое правое место
If a(i) > a(i + 1) Then swap i, i + 1, bool
Next i
End Sub

Private Sub prBack(p As Integer, q As Integer, bool As Boolean)
Dim i As Integer
bool = True
For i = p To q Step -1 'обратный ход. min-элемент займет самое левое место
If a(i) < a(i - 1) Then swap i, i - 1, bool
Next i
End Sub

Вот так я написал две процедуры для прямого и обратного прогонов. Они мне еще не раз пригодятся. А Вы можете, при желании, обойтись и любой одной. Дело вкуса и конкретной решаемой задачи

И как результат привожу два варианта главной процедуры метода пузырьковой сортировки:

Public Sub sortPusir() 'двухпроходный
Dim i As Integer, j As Integer, bSorted As Boolean

For j = LBound(a) To UBound(a) - 1
prForward LBound(a) + j, UBound(a) - j, bSorted
If bSorted Then Exit For 'значит сортировка окончена

prBack UBound(a) - 1 - j, LBound(a) + j, bSorted
If bSorted Then Exit For 'значит сортировка окончена
Next j
End Sub

bSorted флаг сортировки. Его даже инициализировать не надо, т.к. он однозначно устанавливается в true перед каждым прогоном в процедурах прямого и обратного прогона.
Хочу отметить, что хотя цикл по j определен до UBound(a) 1, но реально он даже до середины не дойдет, т.к. при двухпроходном цикле выход по флагу сортировки может осуществиться после любого из прогонов.

Public Sub sortPusir1() 'однопроходный
Dim i As Integer, j As Integer, bSorted As Boolean
For j = LBound(a) To UBound(a) - 1
prBack UBound(a), j + 1, bSorted
If bSorted Then Exit For 'значит сортировка окончена
Next j
End Sub

В однопроходном алгоритме все еще проще. Обратите внимание, что цикл по j идет на увеличение, а прогоны обратные, поэтому все прогоны будут начинаться от самого верхнего индекса массива, а заканчиваться на шаг раньше, чем предыдущий прогон.

Алгоритм Хоара или быстрая, рекурсивная сортировка

Понятное дело, раз алгоритм основан на рекурсии (т.е. при определенных условиях должен вызывать сам себя с измененными входными параметрами), то входные параметры этой процедуры заслуживают особого внимания.

Public Sub sortHoara(p As Integer, q As Integer)

Каким же образом алгоритм проводит грубую сортировку? И как происходит деление на левую и правую части для последующей сортировки?

процедура проверяет входные параметры на соответствие и принимает решение о продолжении или завершении своей работы, а вот (если решила продолжать выполняться) она определяет ОПОРНОЕ ЗНАЧЕНИЕ. Для хранения опорного значения в процедуре выделена отдельная переменная того же типа, что и хранящиеся элементы массива. В моем случае это r As Integer, но если в массиве будут храниться действительные числа или строки, то и опорное значение должно быть того же типа. Кроме того, опорное значение должно быть обязательно «больше или равно» минимальному элементу массива и «меньше или равно» максимальному.

ГРУБАЯ СОРТИРОВКА подразумевает перемещение любого элемента, который больше «опорного значения» в правую часть массива, и любого, который меньше «опорного значения», в левую часть (если сортировка по возрастанию, а иначе - наоборот). В идеальном варианте, «опорное значение» хотелось бы определить таким, чтобы ровно половина элементов массива его превышала, а половина массива была меньше него. Именно при таком варианте количество рекурсивных вызовов было бы минимальным, а, следовательно, и время выполнения сортировки.

А в самом тривиальном случае, r можно присвоить первое попавшееся значение массива, например: r=a(p) или r=a(q). Это будет вполне удовлетворять условиям выбора опорного значения, правда, про оптимальность времени выполнения алгоритма здесь вспоминать не будем. А если честно, то при таком выборе r и большом размере массива при определенных условиях алгоритм не сможет завершиться из-за переполнения стека (ведь каждый рекурсивный вызов это дополнительное наполнение стека).

Но не будем отвлекаться, и продолжаем рассматривать самый тривиальный случай с выбором r=a(p). В несортированном массиве, по теории вероятности, это будет какое-то промежуточное число между максимальным и минимальным элементами массива.

, процедура ищет элемент (т.е. определяет индекс i элемента), который больше r, начиная с начала диапазона.

, процедура ищет элемент (т.е. определяет индекс j элемента), который меньше r, начиная с конца диапазона.

При выполнении условия If i < j And a(i) > a(j) Then swap i, j, False , как видим, происходит обмен (). Учитывая, что шаги 3-5 производятся в цикле Do While , то после окончания цикла, в левой части массива элементы будут располагаться беспорядочно, но среди них не будет ни одного большего r. Точно так же, в правой части, среди беспорядочно расположенных элементов, не будет ни одного меньше r. Это и есть грубая сортировка (по крайней мере, я для себя ее так называю). А значение j разделит массив на левую и правую части.

Следующими шагами процедуры (т.е. алгоритма) будут поочередная обработка левой и правой частей массива, путем рекурсивного вызова себя самой.

Вот пример такой, самой незамысловатой, процедуры сортировки по алгоритму Хоара:

Public Sub sortHoara_s(p As Integer, q As Integer)'самый простой вариант
Dim i As Integer, j As Integer, r As Integer

If p < q Then 'если на входе одинаковые или обратные индексы, то на выход
r = a(p) ' опорное значение
i = p - 1: j = q + 1 ' отступление за границы, чтобы не нарушать while

Do While i < j ' поиск элементов для обмена
Do
i = i + 1
Loop While a(i) < r
'i останавливается на элементе больше опорного (который надо направо)

Do
j = j - 1
Loop While a(j) > r
'j останавливается на элементе меньше опорного (который надо налево)

If i < j And a(i) > a(j) Then swap i, j, False ' обмен
Loop

sortHoara_s p, j ' сортируем левую часть
sortHoara_s j + 1, q ' сортируем правую часть
End If
End Sub

Это понятно. Принимая за опорное значение самый левый элемент отсортированного массива, программа делит массив на две части: в левой части 1 элемент, а в правой весь массив без первого элемента. Вызывается рекурсивно левая часть и заканчивается мгновенно, а вот правая часть опять делится на 1 элемент и все остальное. Итого для завершения задачи должно произойти sizeArr-1 рекурсивных вызовов. При достаточно большом sizeArr и большом количестве элементов массива расположенных в порядке возрастания, такой момент должен наступить неминуемо. Область памяти, отводимая под стек имеет свой предел.

Но если внести незначительные изменения

Public Sub sortHoara(p As Integer, q As Integer)
Dim i As Integer, j As Integer, r As Integer, bSorted As Boolean

If p < q Then 'если на входе одинаковые или обратные индексы, то на выход
If GetSortedMaxMin(p, q, mx, mn) Then Exit Sub
'если участок уже отсортирован - на выход
r = Round((mx + mn) / 2) ' опорное значение. Оптимально по середине

i = p - 1: j = q + 1 ' отступление за границы, чтобы не нарушать while
Do While i < j ' поиск элементов для обмена
Do
i = i + 1
Loop While a(i) < r
'i останавливается на элементе больше опорного (который надо направо)

Do
j = j - 1
Loop While a(j) > r
'j останавливается на элементе меньше опорного (который надо налево)

If i < j And a(i) > a(j) Then swap i, j, False ' обмен
Loop

sortHoara p, j ' сортируем левую часть
sortHoara j + 1, q ' сортируем правую часть
End If
End Sub

Где функция GetSortedMaxMin(p, q, mx, mn) возвращает «true» если заданный диапазон массива уже отсортирован, что ведет к выходу из данного рекурсивного вызова. А если диапазон не отсортирован, то в параметрах по ссылке mx, mn будут находиться максимальный и минимальный элементы массива соответственно, что позволит, более оптимально, определить «опорное значение». Хотя и этот вариант, конечно, не на все случаи жизни Он просто немного лучше предыдущего…

Сортировка Слиянием и Хоара - совмещение

Совмещение алгоритмов Хоара и сортировки слиянием является наиболее оптимальным

Алгоритм сортировки слиянием отлично описан в Википедии.

Не сложно понять, что наибольший эффект от сортировки слиянием получается при объединении двух отсортированных массивов. А в начальный период, когда идет дробление исходного массива на части (как правило, до какой-то определенной величины, а то и до элемента), машинное время и память используются крайне не эффективно.

Как же тут не вспомнить про быструю, рекурсивную сортировку (Хоара). В том алгоритме все наоборот. Очень быстро сортируются сравнительно малые массивы (равномерно перемешанные), а в случае очень больших массивов (особенно если определенная часть уже отсортирована) может происходить рекурсивное переполнение стека.

Вывод: сортировку слиянием следует совмещать с быстрой сортировкой.

Не дробить начальный массив до элемента, а лишь до величины заданной константой MIN_CHUNK_SIZE и эти куски сортировать быстрой сортировкой, ну, а объединять потом, конечно, слиянием.

Таким образом, процедуру, объединяющую два предварительно отсортированных участка массива, можно представить так:

Public Sub merge(p As Integer, m As Integer, q As Integer)
Dim tmp() As Integer 'временный результирующий массив
Dim i As Integer, j As Integer, r As Integer счетчики

ReDim tmp(p To q)
i = p: j = m: r = p

Do
If a(i) < a(j) Then
tmp(r) = a(i)
i = i + 1: r = r + 1
Else
tmp(r) = a(j)
j = j + 1: r = r + 1
End If
Loop While i < m And j <= q 'пока не закончится один из массивов

Do While i < m 'пока не закончится второй из массивов
tmp(r) = a(i)
i = i + 1: r = r + 1
Loop

Do While j <= q 'пока не закончится второй из массивов
tmp(r) = a(j)
j = j + 1: r = r + 1
Loop

For i = p To q перезапись объединенного массива в исходный
a(i) = tmp(i)
Next i
End Sub

р - начальный индекс первого массива, он же будет и начальным индексам объединенного массива;
m (средний) индекс являющийся начальным во втором массиве, поэтому первый отсортированный массив (или участок исходного массива) конечным индексом будет иметь m-1;
q конечный индекс второго отсортированного и объединенного массивов.

А основная процедура сортировки, которая рекурсивно разбивает исходный массив на части длиною меньше константы MIN_CHUNK_SIZE и сортирует их, вызывая метод Хоара, а затем отсортированные части объединяет слиянием, может быть представлена так:

Public Sub mergesort(p As Integer, q As Integer)
Dim leng As Integer, midl As Integer, i As Integer

If p <= q Then 'если на входе одинаковые или обратные индексы, то ошибка - на выход
leng = q - p 'длина участка массива

If leng > MIN_CHUNK_SIZE Then
midl = leng / 2 'индекс элемента, разделяющего массив пополам
mergesort p, p + midl 1 'сортируем левую часть
mergesort p + midl, q ' сортируем правую часть
merge p, p + midl, q ' объединяем слиянием
Else
sortHoara_s p, q ' сортируем Хоаром
End If
End If
End Sub

В этом варианте никогда не происходит переполнения стека (ведь всегда можно уменьшить константу MIN_CHUNK_SIZE) и скорость сортировки достаточно хорошая

ЕЩЁ ПРИМЕРЫ:

Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку .

Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе. Поэтому статья адресована тем, кто только-только заинтересовался теорией алгоритмов и делает в этом направлении первые шаги.

Сегодня поговорим о простейших сортировках обменами.

Если кому интересно, скажу, что есть и другие классы – сортировки выбором, сортировки вставками, сортировки слиянием, сортировки распределением, гибридные сортировки и параллельные сортировки. Есть, кстати, ещё эзотерические сортировки. Это различные фейковые, принципиально нереализуемые, шуточные и прочие псевдо-алгоритмы, про которые я в хабе «IT-юмор» как-нибудь напишу пару статей.

Но к сегодняшней лекции это не имеет отношения, нас сейчас интересуют только простенькие сортировки обменами. Самих сортировок обменами тоже немало (я знаю более дюжины), поэтому мы рассмотрим так называемую пузырьковую сортировку и некоторые другие, с ней тесно взаимосвязанные.

Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет. Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O(n 2 ). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования. Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте, в Википедии или где-нибудь ещё.

Но вернёмся к сортировкам обменами. Упорядочивание происходит в результате многократного последовательного перебора массива и сравнения пар элементов между собой. Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.

Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…

Сортировка и впрямь глупейшая. Просматриваем массив слева-направо и по пути сравниваем соседей. Если мы встретим пару взаимно неотсортированных элементов, то меняем их местами и возвращаемся на круги своя, то бишь в самое начало. Снова проходим-проверяем массив, если встретили снова «неправильную» пару соседних элементов, то меняем местами и опять начинаем всё сызнова. Продолжаем до тех пор пока массив потихоньку-полегоньку не отсортируется.

«Так любой дурак сортировать умеет» — скажете Вы и будете абсолютно правы. Именно поэтому сортировку и прозвали «глупой». На этой лекции мы будем последовательно совершенствовать и видоизменять данный способ. Сейчас у него временная сложность O(n 3 ), произведя одну коррекцию, мы уже доведём до O(n 2 ), потом ускорим ещё немного, потом ещё, а в конце концов мы получим O(n log n) – и это будет вовсе не «Быстрая сортировка»!

Внесём в глупую сортировку одно-единственное улучшение. Обнаружив при проходе два соседних неотсортированных элемента и поменяв их местами, не станем откатываться в начало массива, а невозмутимо продолжим его обход до самого конца.

В этом случае перед нами не что иное как всем известная…

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

Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

Она же сортировка перемешиванием, она же коктейльная сортировка. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки. После этого разворачиваемся на 180 0 и идём в обратную сторону, при этом уже перекатывая в начало не максимум, а минимум. Отсортировав в массиве первый и последний элементы, снова делаем кульбит. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка.

Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

Как видите, если к процессу перебора подойти творчески, то выталкивание тяжёлых (лёгких) элементов к концам массива происходит быстрее. Поэтому умельцы предложили для обхода списка ещё одну нестандартную «дорожную карту».

На сей раз мы не будем сновать по массиву взад-вперёд, а снова вернёмся к идее планомерного обхода слева-направо, но только сделаем шире шаг. На первом проходе элементы с нечётным ключом сравниваем с соседями, зиждущимися на чётных местах (1-й сравниваем со 2-м, затем 3-й с 4-м, 5-й с 6-м и так далее). Затем наоборот – «чётные по счёту» элементы сравниваем/меняем с «нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет». Процесс останавливается тогда, когда после подряд двух проходов по массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни одного обмена. Стало быть, отсортировали.

В обычном «пузырьке» во время каждого прохода мы планомерно выдавливаем в конец массива текущий максимум. Если же передвигаться вприпрыжку по чётным и нечётным индексам, то сразу все более-менее крупные элементы массива одновременно за один пробег проталкиваются вправо на одну позицию. Так получается быстрее.

Разберём последнее покращення* для Сортування бульбашкою** — Сортування гребінцем***. Этот способ упорядочивает весьма шустро, O(n 2 ) – его наихудшая сложность. В среднем по времени имеем O(n log n), а лучшая даже, не поверите, O(n). То есть, весьма достойный конкурент всяким «быстрым сортировкам» и это, заметьте, без использования рекурсии. Впрочем, я обещал, что в крейсерские скорости мы сегодня углубляться не станем, засим умолкаю и перехожу непосредственно к алгоритму.

Небольшая предыстория. В 1980 году Влодзимеж Добосиевич пояснил почему пузырьковая и производные от неё сортировки работают так медленно. Это всё из-за черепашек. «Черепахи» — небольшие по значению элементы, которые находятся в конце списка. Как Вы, возможно, заметили пузырьковые сортировки ориентированы на «кроликов» (не путать с «кроликами» Бабушкина) – больших по значению элементов в начале списка. Они весьма резво перемещаются к финишу. А вот медлительные пресмыкающиеся на старт ползут неохотно. Подгонять «тортилл» можно с помощью расчёски.

image: виноватая черепашка

В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.

Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива разделённого на фактор уменьшения (результат, естественно, округляется до ближайшего целого). Затем, пройдя массив с этим шагом, мы снова делим шаг на фактор уменьшения и проходим по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.

Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения:

Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс.

Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.

* покращення (укр.) – улучшение
** Сортування бульбашкою (укр.) – Сортировка пузырьком
*** Сортування гребінцем (укр.) – Сортировка расчёской