М Е Т О Д Б Ы С Т Р О Й С О Р Т И Р О В К И

Рассмотренные ранее методы прямой выборки и прямого обмена относят к так называемым методам сортировки первого уровня. Существуют также методы второго уровня. Их алгоритмы сложнее, но при этом обеспечивается на один-два порядка более высокое быстродействие программы. К методам второго уровня относятся метод Шелла, метод быстрой сортировки, метод слияния и др. Наиболее эффективным из них является метод быстрой сортировки. Как будет показано ниже, программная реализация этого метода требует использования линейных списков, в данном случае стеков.

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

Алгоритм перестановок по методу Хоара сводится к следующему.

1. Для массива определяется значение срединного элемента .

2. i := 1; j := n.

3. Пока , выполнять i := i + 1.

Пока , выполнять j := j - 1.

4. Если i < j, обменять элементы и .

5. Если i £ j, то i:=i+1, j:=j-1.

6. Шаги 3 .. 5 повторять, пока не будет выполнено отношение i > j.

Работу алгоритма перестановок рассмотрим на примере конкретного массива X:

64 23 18 71 44 15 27 34 55 41 ( n = 10 ) .

1. a = = 44.

2. i = 1; j = 10.

3. i = 1; j = 10.

4. Обмен и :

41 23 18 71 44 15 27 34 55 64

5. i = 2; j = 9.

6. Переход к шагу 3.

3. i = 4; j = 8.

4. Обмен и :

41 23 18 34 44 15 27 71 55 64

5. i = 5; j = 7.

6. Переход к шагу 3.

3. i = 5; j = 7.

4. Обмен и :

41 23 18 34 27 15 44 71 55 64

5. i = 6; j = 6.

6. Переход к шагу 3.

3. i = 7; j = 6.

4. -

5. -

6. Выход.

После окончания работы алгоритма перестановок в массиве X слева от элемента со значением a = 44 расположены элементы , справа - элементы . Переменные i и j на конечном этапе работы алгоритма перестановок разделили массив X на две части: подмассив 1 .. j (1 .. 6) и подмассив i .. n (7 .. 10). Значения границ правого подмассива i..n запоминаются в стеке, подмассив 1 .. j подвергается обработке по рассмотренной выше схеме.

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

Program RapidSorting;

Const Nmax = 1000;

TypeAr = array[1..Nmax] of real;

PoinType = ^Stack;

Stack = record

L,R : word; { левая и правая границы подмассива }

Next : PoinType;

end;

Vari,j,n,Left,Right : word;

X : Ar;

a,Buf : real;

Beg,Run : PoinType;

Begin

В в о д n, X

New(Beg);

Beg^.L:=1; Beg^.R:=n;

Beg^.Next:=nil;

Repeat

Left:=Beg^.L; Right:=Beg^.R;

Run:=Beg; Beg:=Beg^.Next;

Dispose(Run);

Repeat

i:=Left; j:=Right;

a:=x[(Left+Right) div 2];

Repeat

While x[i]<a do

Inc(i);

Whilex[j]>a do

Dec(j);

If i<=j then

Begin

If i<j then

Begin

Buf:=x[i]; x[i]:=x[j]; x[j]:=Buf;

End;

Inc(i); Dec(j);

End;

Untili>j;

If i<Right then

Begin

New(Run);

Run^.l:=i; Run^.R:=Right;

Run^.Next:=Beg; Beg:=Run;

End;

Right:=j;

Until Left>=Right;

Until Beg=nil;

В ы в о д X

End.