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

Первый алгоритм быстрой сортировки 1960 года разработал Ч.А.Р. Хоар (CA.R.Hoare). Этот алгоритм есть одним из найпопу-лярніших, поскольку сравнительно нескладный в реализации, хорошо работает на разнообразных видах входных данных и не требует огромных объемов дополнительной памяти (кроме относительно небольшого стека).

Идея быстрой сортировки такая. В некоторый способ выбирается эталонное значение есть. Значение элементов массива А обмениваются так, что массив разбивается на две участка — левую и правую. Элементы в левом участке имеют значение не больше есть, а в правой — не меньше. После этого достаточно отдельно отсортировать эти две участка.

Существует простой, но довольно эффективный способ выбора есть в участке массива A[L],…, A[R]: есть = A[(L+R) div 2]. Для разбивки используются два индекса — «левый курсор» и и «правый курсор» j. Сначала i=L, j=R; дальше они двигаются навстречу друг другу в такой способ. Значение меньше есть («хорошие») в левой части пропускаются, а на «плохому» движение останавливается. Аналогично после этого в правой части пропускаются значение, которые большие есть. Если и еще не стал больше j, то это означает, что оба они указывают на «плохие» значение. Эти значения обмениваются местами, а курсоры сдвигают навстречу друг другу. Движение курсоров продлевается, пока и не станет больше j. Тогда все элементы от A[L] к А[ j] имеют значение не больше есть, а все от А [и] к A[R] — не меньше. Эти две участка, если их длина больше 1, делятся и сортируются рекурсивно. Если же участок имеет длину 1, то ее уже отсортировано.

Оформим сортировка части массива A [L], …, A[R] такой процедурой:

procedure quicksort(var A:alnt; L,R:word); var e:integer; {эталонное значение} и,j:word; {левый и правый курсоры) begin
и:=L; j:=R; e:=A[(i + j) div 2] ; while i<=j do begin
while A[i]<e do inc(i); while A[j]>e do dec(j); if i<=j then begin swap(A[i],A[j]); inc(i); dec(j); end; end;
{i > j};
if L<j {сортировать левый участок) then quicksort(A,L,j); if i<R {сортировать правый участок) then quicksort(А,и,R); end;

Оценим сложность приведенной реализации быстрой сортировки. Пусть массив А имеет п элементов. В наиболее плохом случае в каждом вызове процедуры quicksort эталонным значением есть меньше всего в участке от A. [L] AO[R] , и разбивка участка массива длиной т дает участка длиной 1 и т — 1, Поскольку т = п, п—1, …, 2, глубина рекурсии достигает 0(и), и при каждом значении т разбивка участка длиной т имеет сложность ОБ(т). Тогда суммарная сложность имеет оценку 0 (w) + 9 (« -1)+…+Є>(2) = 0(л2) .

Тем не менее описанный наиболее плохой случай в реальных данных практически никогда не случается. Для подавляющего большинства данных разбивки участка массива дает две участка с приблизительно равными длинами. Поэтому размеры массивов, которые сортируются, при переходе на следующий уровень рекурсии уменьшаются приблизительно вдвое. Итак, в среднем количество уровней рекурсии оценивается как 0(log п). Очевидно, что на каждом равные рекурсии суммарная сложность есть 0(п), поэтому общая сложность в среднем имеет оценку 0(nlogn).

Многочисленные практические исследования свидетельствуют, что приведенный алгоритм в среднем работает быстрее, чем другие алгоритмы сортировки, которые имеют сложность наиболее плохого случая O(n)ogri) . Быстрая сортировка не сохраняет взаимного порядка одинаковых значений, т.е. есть неустойчивым.

Для выбора эталонного значения существует много способов, а не только выбор A[(L + R)/2). Если эталонным есть одно со значений в сортированной части массива, ведь это разрешает не беспокоиться о предотвращении выхода за границы сортированной часть и не проверять дополнительных условий.

Выбор «золотой середины» (значение, которое должных быть посредине, или медиана) требует немалых дополнительных усилий и может вообще ухудшить оценку сложности. Тем не менее довольно эффективным есть выбор среднего с трех значений — первого (с индексом L), последнего {R) и срединного ((І + R)/2). Для этого перед выбором эталону их можно обменять местами таким образом.

if A[L] > A[(L+R) div 2]
then swap (A[L] ,A[ (L+R) div 2] ) ;
if A[(L+R) div 2] > A[R]
then swap (A[(L+R) div 2],A[R]>;
if A[L] > A[(L+R) div 2]
then swap(A[L],A[(L+R) div 2]);
e := A[(L+R) div 2];

Еще два способа выбора эталонное значение приведено в задачах к этой главе.

Итеративная версия алгоритма. Запишем итеративную процедуру, в которой явным образом реализуем обработку стека, необходимую для выполнения рекурсивной процедуры. Смоделируем программный стек с помощью массива Stack, в котором будем сохранять левые и правые границы сортированных підмасивів. Сначала присвоим элементам массива Stack значение 0 с помощью стандартной подпрограммы f illchar.

procedure Quicksort(var A:alnt; nrword); var i, j, L, R, top : word; e : integer;
Stack : array[1..N_max,1..2] of word; Begin
FillChar(Stack,SizeOf (Stack) ,0) ;
top:=l; {индекс верхушки стека}
Stack[top,1] := 1; Stack[top,2] := N;
while top>0 do
begin
L:«Stack[top,1]; R:=Stack[top,2];
dec(top);
e:=A[(L+R) div 2];
и:»L; j:=R;
repeat
while (A[i]<e) do inc(i); while (A[j]>e) do dec(j); if i<=j then begin Swap(A[i],A[j]); inc(i); dec(j); end; until i>=j; if L<j then begin inc(top);
Stack[top,1]:=L; Stack[top,2]:=j; end;
if i<R then begin inc(top); Stack[top,1]:=i; Stack[top,2]:=R;
end; End; End;