Sort(1,n);

BEGIN

End

Begin

Repeat

Begin

End

Begin

End;

Begin

BEGIN

End;

Begin

Begin

Label 13;

Var i,j:word;

i:=l; j:=2*i; x:=a[i];

While j<=r Do

If j<r Then

If a[j]<a[j+1] Then j:=j+1;

If x>=a[j] Then Goto 13;

a[i]:=a[j]; i:=j; j:=2*i;

13: a[i]:=x

End;{Sift}

l:=(n div 2)+1; r:=n;

While l>1 Do

l:=l-1; Sift

While r>1 Do

x:=a[1]; a[1]:=a[r]; a[r]:=x;

r:=r-1; Sift

END;{Heap_Sort}

Обменная сортировка разделением (быстрая сортировка).

Выбирается любой произвольный элемент массива, далее массив просматривается слева направо до тех пор пока не будет найден элемент больший выбранного; а затем просмотрим его справа налево, пока не найдем элемент меньший выбранного. Найденные элементы поменяем местами. Затем продолжим процесс “просмотра с обменом”, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами. Описанный алгоритм применяется к обоим этим частям, в результате чего последовательность разбивается на 4 части. Алгоритм применяется к каждой четвертинке и т.д. Разделение заканчивается, когда в каждой части остается 1 элемент.

В процедуре Quick_Sort вызывается процедура Sort, которая реализует алгоритм разделения и обмена для одной части массива.

Procedure Quick_Sort(n:word;Var a:massiv);

Procedure Sort(l,r:word);

Var w,x:integer;

i,j:word;

i:=l; j:=r;

x:=a[(l+r) div 2];

While a[i]<x Do i:=i+1;

While a[j]>x Do j:=j-1;

If i<=j Then

w:=a[i]; a[i]:=a[j]; a[j]:=w;

i:=i+1; j:=j-1

Until i>j;

If l<j Then Sort(l,j);

If i<r Then Sort(i,r);

End;{Sort}

END;{Quick_Sort}