Do
Просмотр от hi до значения < med_value.
Do While list(hi) >= med_value
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
list(lo) = med_value
Exit Do
End If
‘ Поменять местами значения lo и hi.
list(lo) = list(hi)
‘ Просмотр от lo до значения >= med_value.
lo = lo + 1
Do While list(lo) < med_values
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
list(hi) = med_value
Exit Do
End If
‘ Поменять местами значения lo и hi.
list(hi) = list(lo)
Loop
‘ Рекурсивная сортировка двух подлистов.
QuickSort list(), min, lo - 1
QuickSort list(), lo + 1, max
End Sub
=========240
Есть несколько важных моментов в этой версии алгоритма, которые стоит упомянуть. Во‑первых, значение med_value для деления списка не входит ни в один подсписок. Это означает, что в двух подсписках содержится на одни элемент меньше, чем в исходном списке. Т.к. число рассматриваемых элементов уменьшается, то в конечном итоге алгоритм завершит работу.
Эта версия алгоритма использует в качестве разделителя первый элемент в списке. В идеале, это значение должно было бы находиться где‑то в середине списка, так чтобы два подсписка были примерно равного размера. Тем не менее, если элементы первоначально почти отсортированы, то первый элемент — наименьший в списке. При этом алгоритм не поместит ни одного элемента в первый подсписок, и все элементы во второй. Последовательность действий алгоритма будет примерно такой, как показано на рис. 9.4.
В этом случае каждый вызов подпрограммы требует порядка O(N) шагов для перемещения всех элементов во второй подсписок. Т.к. алгоритм рекурсивно вызывает себя N - 1 раз, время его выполнения будет порядка O(N2), что не лучше, чем у ранее рассмотренных алгоритмов. Ситуацию еще более ухудшает то, что уровень вложенности рекурсии алгоритма N - 1. Для больших списков огромная глубина рекурсии приведет к переполнению стека и сбою в работе программы.
=========242
@Рис. 9.4. Быстрая сортировка упорядоченного списка
Существует много стратегий выбора разделительного элемента. Можно использовать элемент из середины списка. Это может оказаться неплохим выбором, тем не менее, может оказаться и так, что это окажется наименьший или наибольший элемент списка. При этом один подсписок будет намного больше, чем другой, что приведет к снижению производительности до порядка O(N2) и глубокому уровню рекурсии.
Другая стратегия может заключаться в том, чтобы просмотреть весь список, вычислить среднее арифметическое всех значений, и использовать его в качестве разделительного значения. Этот подход будет давать неплохие результаты, но потребует дополнительных усилий. Дополнительный проход со сложностью порядка O(N) не изменит теоретическое время выполнения алгоритма, но снизит общую производительность.
Третья стратегия — выбрать средний из элементов в начале, конце и середине списка. Преимущество этого подхода в быстроте, потому что потребуется выбрать всего три элемента. При этом гарантируется, что этот элемент не является наибольшим или наименьшим в списке, и вероятно окажется где‑то в середине списка.
И, наконец, последняя стратегия, которая используется в программе Sort, заключается в случайном выборе элемента из списка. Возможно, это будет неплохим выбором. Даже если это не так, возможно на следующем шаге алгоритм, возможно, сделает лучший выбор. Вероятность постоянного выпадения наихудшего случая очень мала.
Интересно, что этот метод превращает ситуацию «небольшая вероятность того, что всегда будет плохая производительность» в ситуацию «всегда небольшая вероятность плохой производительности». Это довольно запутанное утверждение объясняется в следующих абзацах.
При использовании других методов выбора точки раздела, существует небольшая вероятность того, что при определенной организации списка время сортировки будет порядка O(N2), Хотя маловероятно, что подобная организация списка в начале сортировки встретится на самом деле, тем не менее, время выполнения при этом будет определенно порядка O(N2), неважно почему. Это то, что можно назвать «небольшой вероятностью того, что всегда будет плохая производительность».
===========242
При случайном выборе точки раздела первоначальное расположение элементов не влияет на производительность алгоритма. Существует небольшая вероятность неудачного выбора элемента, но вероятность того, что это будет происходить постоянно, чрезвычайно мала. Это можно обозначить как «всегда небольшая вероятность плохой производительности». Независимо от первоначальной организации списка, очень маловероятно, что производительность алгоритма будет порядка O(N2).
Тем не менее, все еще остается ситуация, которая может вызвать проблемы при использовании любого из этих методов. Если в списке очень мало различных значений в списке, алгоритм заносит множество одинаковых значений в подсписок при каждом вызове. Например, если каждый элемент в списке имеет значение 1, последовательность выполнения будет такой, как показано на рис. 9.5. Это приводит к большому уровню вложенности рекурсии и дает производительность порядка O(N2).
Похожее поведение происходит также при наличии большого числа повторяющихся значений. Если список состоит из 10.000 элементов со значениями от 1 до 10, алгоритм довольно быстро разделит список на подсписки, каждый из которых содержит только одно значение.
Наиболее простой выход — игнорировать эту проблему. Если вы знаете, что данные не имеют такого распределения, то проблемы нет. Если данные имеют небольшой диапазон значений, то вам стоит рассмотреть другой алгоритм сортировки. Описываемые далее в этой главе алгоритмы сортировки подсчетом и блочной сортировки очень быстро сортируют списки, данных в которых находятся в узком диапазоне.
Можно внести еще одно небольшое улучшение в алгоритм быстрой сортировки. Подобно многих другим более сложным алгоритмам, описанным далее в этой главе, быстрая сортировка — не самый лучший выбор для сортировки небольших списков. Благодаря своей простоте, сортировка выбором быстрее при сортировке примерно десятка записей.
@Рис. 9.5. Быстрая сортировка списка из единиц
==========243
@Таблица 9.3. Время быстрой сортировки 20.000 элементов
Можно улучшить производительность быстрой сортировки, если прекратить рекурсию до того, как подсписки уменьшатся до нуля, и использовать для завершения работы сортировку выбором. В табл. 9.3 приведено время, которое занимает выполнение быстрой сортировки 20.000 элементов на компьютере с процессором Pentium с тактовой частотой 90 МГц, если останавливать сортировку при достижении подсписками определенного размера. В этом тесте оптимальное значение этого параметра было равно 15.
Следующий код демонстрирует доработанный алгоритм:
Public Sub QuickSort*List() As Long, ByVal min As Long, ByVal max As Long)
Dim med_value As Long
Dim hi As Long
Dim lo As Long
Dim i As Long
‘ Если в списке больше, чем CutOff элементов,
‘ завершить его сортировку процедурой SelectionSort.
If max - min < cutOff Then
SelectionSort List(), min, max
Exit Sub
End If
‘ Выбрать разделяющее значение.
i = Int((max - min + 1) * Rnd + min)
med_value = List(i)
‘ Переместить его вперед.
List(i) = List(min)
lo = min
hi = max
Do
‘ Просмотр сверху вниз от hi до значения < med_value.
Do While List(hi) >= med_value
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
List(lo) = med_value
Exit Do
End If
‘ Поменять местами значения lo и hi.
List(lo) = List(hi)
‘ Просмотр снизу вверх от lo до значения >= med_value.
lo = lo + 1
Do While List(lo) < med_value
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
List(hi) = med_value
Exit Do
End If
‘ Поменять местами значения lo и hi.
List(hi) = List(lo)
Loop
‘ Сортировать два подсписка.
QuickSort List(), min, lo - 1
QuickSort List(), lo + 1, max
End Sub
=======244
Многие программисты выбирают алгоритм быстрой сортировки, т.к. он дает хорошую производительность в большинстве обстоятельств.
Как и быстрая сортировка, сортировка слиянием (mergesort) — это рекурсивный алгоритм. Он также разделяет список на два подсписка, и рекурсивно сортирует подсписки.
Сортировка слиянием делит список пополам, формируя два подсписка одинакового размера. Затем подсписки рекурсивно сортируются, и отсортированные подсписки сливаются, образуя полностью отсортированный список.
Хотя этап слияния легко понять, это наиболее интересная часть алгоритма. Подсписки сливаются во временный массив, и результат копируется в первоначальный список. Создание временного массива может быть недостатком, особенно если размер элементов велик. Если размер временного размера очень большой, он может приводить к обращению к файлу подкачки и значительно снижать производительность. Работа с временным массивом также приводит к тому, что большая часть времени уходит на копирование элементов между массивами.
Так же, как и в случае с быстрой сортировкой, можно ускорить выполнение сортировки слиянием, остановив рекурсию, когда подсписки достигают определенного минимального размера. Затем можно использовать сортировку выбором для завершения работы.
=========245
Public Sub Mergesort(List() As Long, Scratch() As Long, _
ByVal min As Long, ByVal max As Long)
Dim middle As Long
Dim i1 As Long
Dim i2 As Long
Dim i3 As Long
‘ Если в списке больше, чем CutOff элементов,
‘ завершить его сортировку процедурой SelectionSort.
If max - min < CutOff Then
Selectionsort List(), min, max
Exit Sub
End If
‘ Рекурсивная сортировка подсписков.
middle = max \ 2 + min \ 2
Mergesort List(), Scratch(), min, middle
Mergesort List(), Scratch(), middle + 1, max
‘ Слить отсортированные списки.
i1 = min ‘ Индекс списка 1.
i2 = middle + 1 ‘ Индекс списка 2.
i3 = min ‘ Индекс объединенного списка.
Do While i1 <= middle And i2 <= max
If List(i1) <= List(i2) Then
Scratch(i3) = List(i1)
i1 = i1 + 1
Else
Scratch(i3) = List(i2)
i2 = i2 + 1
end If
i3 = i3 + 1
Loop
‘ Очистка непустого списка.
Do While i1 <= middle
Scratch(i3) = List(i1)
i1 = i1 + 1
i3 = i3 + 1
Loop
Do While i2 <= max
Scratch(i3) = List(i2)
i2 = i2 + 1
i3 = i3 + 1
Loop
‘ Поместить отсортированный список на место исходного.