Быстрая сортировка (Quick Sort)

Относится к методам обменной сортировки. В основе лежит методика разделения ключей по отношению к выбранному.

Слева от 6 располагают все ключи с меньшими, а справа - с большими или равными 6 (рис. 6.4).

Sub Sort (L, R)

i = L

j = R

x = a((L + R) div 2)

repeat

while a(i) < x do

i = i + 1

endwhile

while a(j) > x do

j = j - 1

endwhile

if i <= j then

y = a(i)

a(i) = a(j)

a(j) = y

i = i + 1

j = j - 1

endif

until i > j

if L < j then

sort (L, j)

endif

if i < R then

sort (i, R)

endif

return

sub QuickSort

sort (1, n)

return

procedure Sort (L, R: integer);

begin

i := L;

j := r;

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

repeat

while a[i] < x do

i := i + 1;

while a[j] > x do

j := j - 1;

if i <= j then

begin

y := a[i];

a[i] := a[j];

a[j] := y;

i := i + 1;

j := j - 1

end;

until i > j;

if L < j then sort (L, j);

if i < r then sort (i, r);

end;

procedure QuickSort;

begin

sort (1, n);

end;

Эффективность алгоритма:

О(n log n) - самый эффективный метод.

Содержание раздела