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

В пузырьковой сортировке производились обмены ключей (записей) в соседних позициях. В пирамидальной сортировке такие обмены совершались между ключами в позициях, связанных друг с другом бинарным деревом. Алгоритм сортировки Хоора или сортировки с разделение или быстрой сортировки использует иной механизм выбора значений для обменов. В названиях алгоритма подчеркиваются автор, или способ сортировки – последовательного дробления массива на части, или его эффективность. В подавляющем большинстве случаев быстрая сортировка дает лучшие временные результаты по сравнению с другими способами. Однако для нее нет гарантированной трудоемкости типа O(n log₂ n), а в отдельных случаях ее трудоемкость достигает O(n²) и не может быть снижена. В ситуациях жесткого временного ограничения сортировку следует применять весьма осмотрительно.

Суть способа. Пусть – одномерный массив, а x – его элемент. Сначала выясним, как разбить массив S на две непустые непересекающиеся части S₁ и S₂ (S₁ S₂=S) так, чтобы в S₁ оказались элементы, не превосходящие x , а в S₂ – не меньше x: . Для этого рассмотрим пример. Пусть в массиве S зафиксирован элемент x=14. Просматриваем массив слева нап раво, пока не найдем . . Просматриваем массив справа налево, пока не найдем . . Меняем местами a и b. Продолжая этот процесс, придем к последовательности, разделенной на две части S₁ и S₂:

О

Dim S() As Integer

Const n As Integer = 10

Sub Быстрая_сортировка() 'Отладочный вариант

Dim T1(1 To 13) As Integer, T2(1 To 13) As Integer

Dim i As Integer, j As Integer, k As Integer, a As Integer, b As Integer, x As Integer, var As String

ReDim S(1 To n): S(1)=6: S(2)=23: S(3)=17: S(4)=8: S(5)=14: S(6)=25: S(7)=6: S(8)=3: S(9)=30: S(10)=7

'For j = 1 To n: S(j) = Int(Rnd(Time) * 1000): Next j

var = "Исходные:": For j = 1 To n: var = var & " " & Str(S(j)): Next j: MsgBox var

k = 1: T1(1) = 1: T2(1) = n: 'Инициализация стека

Do: a = T1(k): b = T2(k): k = k – 1 'Чтение из стека (выбор адресов не отсортированной правой части)

Do: i = a - 1: j = b + 1: x = S((a + b)\2) 'Разделение массива или его части

Do: Do: i = i + 1: Loop While S(i) < x: Do: j = j - 1: Loop While x < S(j)

If i >= j Then 'Смыкание или перехлест границ частей массива

If i <> j Then i = i – 1 'Раздвижка границ

j = j + 1: GoTo 1

Else

Swap S(i), S(j) 'Обмен "чужих" на "своих"

End If

Loop While j - i > 2

If j - i = 2 Then 'Выяснение граничной ситуации

If S(i + 1) < x Then 'Люфт границ

i = i + 1

Else 'Четкое разделение границ

j = j - 1

End If

End If

1: If j < b Then 'Правая часть массива не исчерпана

k = k + 1: T1(k) = j: T2(k) = b 'Запись в стек (фиксация не отсортированной правой части)

End If

b = i 'Фиксация правой границы еще не отсортированной левой части

Loop While a < b 'Левая часть не исчерпана

Loop While k > 0 'Переход к анализу правой части

var = "Отсортированные:": For j = 1 To n: var = var & " " & Str(S(j)): Next j: MsgBox var

End Sub

Sub Swap(ByRef x As Integer, ByRef y As Integer) 'Обмен значениями

Dim m As Integer

m = x: x = y: y = m

End Sub

бозначим через p позицию разделения массива. Элементы от 1-го до p-го включительно относятся к S₁, а остальные – к S₂. Значение x для разделения будем выбирать из середины массива. При четном числе элементов имеются два кандидата на роль x, из них берем элемент с меньшим индексом. Если, аналогично рассмотренному разбиению, продолжить этот процесс для полученных частей массива, а затем и для частей вновь полученных частей, то в конечном итоге получим отсортированный массив. Но при этом необходимо хранить адреса разделяемых частей массива. Если после очередного разбиения продолжать работу с меньшей из полученных частей, отправляя на хранение адреса начала и конца второй части, то потребуется немного дополнительной памяти – не более адресов (для n4000 число адресов не более 12).

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

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

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

3). Четкое разделение – границы не смыкаются, т.е. приходятся на соседние элементы.

4). Люфт, когда между границами располагается один непроанализированный элемент.

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