В статье разберем 9 видов сортировок, рассмотрим суть этих алгоритмов. Скорости, сложность алгоритмов и практическое их применение оставим за скобками. Задача статьи показать, что одну и туже задачу можно решать различными способами, показать практическое применение языка VBA и помочь начинающим в его освоении.
Скачать файлик можно по кнопке выше. Поехали!
Перед тем как начинать писать алгоритмы немного подготовимся. Создадим общую константу n для хранения размера массивов. Вставим на лист диаграмму, чтобы отслеживать как все работает. В коде объявим объект нашей диаграммы, на которой будем просматривать ход процесса сортировки. Чтобы не дублировать код в каждом алгоритме сортировки мы будем использовать процедуру инициализации Init().
Option Explicit Const n As Long = 25 Dim Chrt As ChartObject '************************************************************** ' Sub : Init ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Инициализация '************************************************************** Sub Init() Set Chrt = ActiveSheet.ChartObjects(1) End Sub
Чтобы наша диаграмма с результатом не подвисала и обновлялась напишем такую функцию.
'************************************************************** ' Sub : ChartRefresh ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Обновление диаграммы '************************************************************** Sub ChartRefresh() Chrt.Activate Application.Calculate DoEvents End Sub
В качестве массивов будем использовать диапазон ячеек A1:Y1. Напишем еще одну коротенькую процедуру для перемешивания этого массива, точнее заполнения его числами от 1 до 25 в случайном порядке.
'************************************************************** ' Sub : RandomArray ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Перемешивание массива '************************************************************** Sub RandomArray() Dim coll As New Collection Dim rndVal As Long Randomize Do While coll.count < n rndVal = CLng((n - 1) * Rnd) + 1 On Error Resume Next coll.Add rndVal, CStr(rndVal) If Err.Number = 0 Then Cells(1, coll.count) = rndVal Err.Clear Loop End Sub
Теперь все готово, давайте писать алгоритмы сортировки.
Пузырьковая сортировка (или сортировка простыми обменами) пожалуй самый неэффективный алгоритм сортировки и в тоже время пожалуй самый известный.
Суть алгоритма в прохождении в цикле по всем элементами массива и в попарном сравнении текущего элемента со следующим. Если текущий элемент массива больше (для сортировки по возрастанию и меньше для сортировки по убыванию) чем следующий, то эти два элемента меняются друг с другом местами. Ход алгоритма смотрите на следующей диаграмме.
Вот код сортировки данным алгоритмом на VBA. Еще стоит обратить внимание на переменную Flag она служит индикатором того, что массив досрочно отсортирован и можно заранее выйти из цикла и сократить вычислительные ресурсы.
'************************************************************** ' Sub : BubbleSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Сортировка простыми обменами, сортировка пузырьком '************************************************************** Sub BubbleSort() Dim i As Long Dim j As Long Dim Flag As Boolean Init For i = 1 To n - 1 Flag = False For j = 1 To n - i If Cells(1, j) > Cells(1, j + 1) Then Swap Cells(1, j), Cells(1, j + 1): Flag = True Next If Not Flag Then Exit For Next End Sub
Далее описана процедура Swap для перестановки ячеек местами. После перестановки ячеек вызывается процедура ChartRefresh обновления диаграммы.
'************************************************************** ' Sub : Swap ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Перестановка ячеек '************************************************************** Sub Swap(A As Range, B As Range) Dim C As String C = A A = B B = C ChartRefresh End Sub
Этот алгоритм является разновидностью пузырьковой сортировки. Также этот алгоритм называют Шейкерной сортировкой или двунаправленной. Основное отличие от обычной сортировки пузырьком в том, что массив сначала просматривается слева направо и максимальный элемент перемещается вправа, а после мы проходим по массиву справа налево (от последнего отсортированного элемента) и наименьший элемент перемещается влево. Вот на графике отчетливо это видно.
Алгоритм немного больше, но по сложности аналогичный, вот его код на VBA.
Sub ShakerSort() Dim left As Long Dim right As Long Dim count As Long Dim i As Long Init left = 1 right = n count = 0 Do While left < right For i = left To right - 1 count = count + 1 If Cells(1, i) > Cells(1, i + 1) Then Swap Cells(1, i), Cells(1, i + 1) Next right = right - 1 For i = right To left + 1 Step -1 count = count + 1 If Cells(1, i - 1) > Cells(1, i) Then Swap Cells(1, i - 1), Cells(1, i) Next left = left + 1 Loop End Sub
Тоже достаточно простой алгоритм сортировки. Суть его заключается в поиске минимального значения (максимального для сортировки по убыванию) и обмене найденного значения с первым неотсортированным значением. Т.е. нашли первое минимальное значение, поменяли его с первым элементом, нашли второе минимальное - поменяли со вторым элементом. График получается следующий:
'************************************************************** ' Sub : SelectionSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Сортировка выбором '************************************************************** Sub SelectionSort() Dim i As Long Dim j As Long Dim iMin As Long Init For i = 1 To n iMin = i For j = i To n If Cells(1, j) < Cells(1, iMin) Then iMin = j Next If iMin <> i Then Swap Cells(1, i), Cells(1, iMin) Next End Sub
Можно ускорить алгоритм сортировки пузырьком объединив его с алгоритмом сортировки выбором. Для этого нужно определять минимальный элемент во внутреннем цикле и после каждого прохода по списку обменивать найденный минимальный элемент с первым неотсортированным слева. Таким образом, мы сокращаем в 2 раза число перестановок, но при этом увеличиваем в 2 раза число сравнений.
Код отличается только 2 строчками:
'************************************************************** ' Sub : BubbleSortWhithSelection ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Объединение сортировки пузырьком и сортировки выбором '************************************************************** Sub BubbleSortWhithSelection() Dim i As Long Dim j As Long Dim iMin As Long Init For i = 1 To n - 1 iMin = i For j = i To n - i If Cells(1, j) > Cells(1, j + 1) Then Swap Cells(1, j), Cells(1, j + 1) If Cells(1, j) < Cells(1, iMin) Then iMin = j Next If iMin <> i Then Swap Cells(1, i), Cells(1, iMin) Next End Sub
Вот определение сортировки с википедии
Это алгоритм, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Другими словами мы во внешнем цикле проходим по всем элементам массива, а во внутреннем цикле сравниваем правый элемент с уже отсортированными элементами слева и перемещаем его при необходимости. Вот как это выглядит визуально:
Код тоже думаю окажется для вас достаточно простым.
'************************************************************** ' Sub : InsertionSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Сортировка вставками '************************************************************** Sub InsertionSort() Dim i As Long Dim j As Long Init For i = 2 To n j = i Do While j > 1 If Cells(1, j) > Cells(1, j - 1) Then Exit Do Swap Cells(1, j), Cells(1, j - 1) j = j - 1 Loop Next End Sub
Визуально отличия от сортировки вставками нет, однако в код совершенно другой так как нет никаких вложенных циклов. Алгоритм в цикле проходит по всем элементам, сравнивая текущий элемент с предыдущим. Если элементы стоят верно переходит к следующему, если нет, меняет их местами и переходит к предыдущему элементу.
'************************************************************** ' Sub : GnomeSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Гномья сортировка '************************************************************** Sub GnomeSort() Dim i As Long Dim j As Long Init i = 2 j = 2 Do While i < n + 1 If Cells(1, i - 1) < Cells(1, i) Then i = j j = j + 1 Else Swap Cells(1, i - 1), Cells(1, i) i = i - 1 If i = 1 Then i = j j = j + 1 End If End If Loop End Sub
Простые алгоритмы сортировки мы разобрали, теперь давайте рассмотрим более сложные виды сортировок. Хотя главное понять суть алгоритма и его реализация уже не будет казаться сложной.
Суть алгоритма сортировки слиянием состоит в том, чтобы разбить исходный массив на более мелкие массивы, отсортировать каждый по отдельности, а после объединить результаты.
Для этого первоначальный массив разбивается на 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), которая сортирует и объединяет массив обратно.
'************************************************************** ' Function : MergeSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Рекурсивная функция сортировки слиянием '************************************************************** Function MergeSort(rng As Range) Dim left As Range Dim right As Range Dim result As Range Dim i As Long Dim middle As Long If rng.Cells.count = 1 Then Set MergeSort = rng Exit Function Else middle = CLng(rng.Cells.count / 2) ' Разделяем диапазон на 2 части Set left = Range(rng.Columns(1), rng.Columns(middle)) Set right = Range(rng.Columns(middle + 1), rng.Columns(rng.Columns.count)) ' Рекурсивно проходим этой же функцией по каждой части left = MergeSort(left) right = MergeSort(right) ' Объединяем части обратно в единое целое MergeSort = Merge(left, right) End If End Function
В качестве сортировки и объединения можно использовать различные алгоритмы, например такой. Если кто-то предложит более изящное решение - пишите в комментариях.
'************************************************************** ' Function : Merge ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Функция сортирует и объединяет диапазон '************************************************************** Function Merge(left As Range, right As Range) As Range Dim i As Long Dim count As Long Dim result Dim sizeLeft As Long Dim sizeRight As Long Dim FirstRng As Range Set FirstRng = left.Cells(1, 1) sizeLeft = left.count sizeRight = right.count ReDim result(1 To sizeLeft + sizeRight) i = 1 Do While sizeLeft > 0 And sizeRight > 0 If left.Columns(1) <= right.Columns(1) Then result(i) = left.Columns(1) If sizeLeft > 1 Then Set left = left.Offset(, 1).Resize(, left.Columns.count - 1) sizeLeft = sizeLeft - 1 Else result(i) = right.Columns(1) If sizeRight > 1 Then Set right = right.Offset(, 1).Resize(, right.Columns.count - 1) sizeRight = sizeRight - 1 End If i = i + 1 Loop Do While sizeLeft > 0 result(i) = left.Columns(1) If sizeLeft > 1 Then Set left = left.Offset(, 1).Resize(, left.Columns.count - 1) sizeLeft = sizeLeft - 1 i = i + 1 Loop Do While sizeRight > 0 result(i) = right.Columns(1) If sizeRight > 1 Then Set right = right.Offset(, 1).Resize(, right.Columns.count - 1) sizeRight = sizeRight - 1 i = i + 1 Loop For i = 1 To UBound(result) FirstRng.Offset(, i - 1) = result(i) ChartRefresh Next Set Merge = FirstRng.Resize(, UBound(result)) End Function
Так как функция у нас рекурсивная, то первый ее запуск необходимо сделать из отдельной процедуры, вот так:
'************************************************************** ' Sub : StartMergeSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Запуск сортировки слиянием '************************************************************** Sub StartMergeSort() Init MergeSort Range(Cells(1, 1), Cells(1, n)) End Sub
Алгоритм быстрой сортировки - один из самых быстрых и эффективных и часто используется в практике. При этом он достаточно простой.
Суть алгоритма в следующем:
На визуализации к сожалению что-то разглядеть сложно. Алгоритм достаточно быстро отрабатывает:
Вот код данного алгоритма на VBA.
'************************************************************** ' Sub : QuickSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Рекурсивная функция для быстрой сортировки '************************************************************** Sub QuickSort(rng As Range, lo, hi) Dim p As Long If lo < hi Then p = Partition(rng, lo, hi) Call QuickSort(rng, lo, p) Call QuickSort(rng, p + 1, hi) End If End Sub
'************************************************************** ' Function : Partition ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Выбор опорного элемента для быстрой сортировки '************************************************************** Function Partition(rng As Range, lo, hi) Dim i As Long Dim j As Long Dim pivot i = lo j = hi pivot = (rng.Cells(1, lo) + rng.Cells(1, hi)) / 2 Do Do While rng.Cells(1, i) < pivot i = i + 1 Loop Do While rng.Cells(1, j) > pivot j = j - 1 Loop If i >= j Then Partition = j Exit Function End If Swap rng.Cells(1, i), rng.Cells(1, j) Loop End Function
Запуск рекурсивной функции быстрой сортировки запустим из отдельного метода.
'************************************************************** ' Sub : StartQuickSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Запуск быстрой сортировки '************************************************************** Sub StartQuickSort() Init QuickSort Range(Cells(1, 1), Cells(1, n)), 1, n End Sub
Пирамидальная сортировка или как еще ее называют "Сортировка кучей" использует в своем алгоритме двоичное дерево.
Это такое дерево, для которого выполнены следующие условия:
Вот пример дерева, которое можно найти на википедии:
Это дерево можно представить в виде следующего массива, где для любого элемента A[i] потомками являются элементы A[2i] и A[2i+1].
Т.е. для каждого элемента кучи справедливы следующие условия: A[i] >= A[2i] и A[i] >= A[2i+1].
Алгоритм пирамидальной сортировки состоит из следующих шагов:
Вот визуальное отображение выполнения этого алгоритма:
Ниже код пирамидальной сортировки на VBA. Который формирует двоичную кучу и корень этой кучи переносит в конец последовательности. Так происходит n раз.
'************************************************************** ' Sub : HeapSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Пирамидальная сортировка '************************************************************** Sub HeapSort() Dim i As Long Dim j As Long Init For i = 1 To n For j = CInt((n + 1) / 2) - CInt(i / 2) To 1 Step -1 If 2 * j + 1 <= n - i + 1 Then If Cells(1, 2 * j) > Cells(1, 2 * j + 1) Then If Cells(1, j) < Cells(1, 2 * j) Then Swap Cells(1, j), Cells(1, 2 * j) End If Else If Cells(1, j) < Cells(1, 2 * j + 1) Then Swap Cells(1, j), Cells(1, 2 * j + 1) End If End If Else If 2 * j <= n - i + 1 Then If Cells(1, j) < Cells(1, 2 * j) Then Swap Cells(1, j), Cells(1, 2 * j) End If End If End If Next Swap Cells(1, 1), Cells(1, n - i + 1) Next End Sub