9 алгоритмов сортировки на VBA

О чем пойдет речь

В статье разберем 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

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

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

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

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

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

Вот код данного алгоритма на 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

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

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

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

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

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

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

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

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

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

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

Ниже код пирамидальной сортировки на 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