Быстрая сортировка Хоару

В методе пузырька последовательность сравнений предопределена и на следующем шаге мы не используем ту информацию, которую могли бы извлечь из сравнений этого шага.

Рассмотрим стратегию, которая это использует.

2 6 7 10 8 1 5 7

1 2

2 6

|

5 6 7 8 10

1 2 5 6 7 8 10

i à ß j

i=left =1 j=right=8

начинаем сравнивать i j элементы.

Если левый i-тый элемент оказался неупорядочен относительно правого, т.е. j – они меняются местами. После обмена начинает увеличиться i или уменьшаться j, та, которая не изменялась до обмена., а другая замораживается до следующего обмена. Стадия завершается в случае j=i. Рассмотрим эту ситуацию.

В этот момент слева от этой позиции отсутствуют элементы, превышающие, а справа отсутствуют элементы меньшие. Что в каждом сравнении использовался первый элемент, который назовем опорным. Опорный элемент занял свой окончательное положение в сортируемой последовательности (т.к. слева нету элементов больших, а справа - меньших). К каждой из двух под последовательностей (левую и правую относительно опорного) можно применить ту ж процедуру. Рекурсивно применим данную процедуру до тех пор, пока right-left > 2

Procedure quicksort(left,right:integer);

Var j,i:integer;

Begin i:=left; J:=right;

Repeat

While (i<j) K[i] < K[j] do j--;

If i<j then R[i] ß à R[j];

If i<j then

While(i<j) and (k[i] < k[j]) do i++;

If i<j then r[i] ß à R[j];

Until i=j;

If (i-left) > 1 then quicksort(left,i-1);

If (right-j) > 1 then quicksort(i+1,right);

End;

Begin quciksort();