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

Алгоритм быстрой сортировки является, по-видимому, самым эффективным алгоритмом сортировки массивов. В этом алгоритме для сортировки элементов массива X[1],X[2],...,X[N] из этих элементов выбирается некоторый элемент, значение которого берется в качестве опорного значения v, относительно которого переупорядочиваются элементы массива. Переупорядочивание заключается в том, чтобы для некоторого индекса j все элементы X[1],...,X[j] имели значение меньше v, а все элементы X[j+1],...,X[N] имели значение больше или равно v. Затем процедура рекурсивно применяется к частям массива, состоящим из элементов X[1],...,X[j] и X[j+1],...,X[N]. Желательно выбрать опорное значение так, чтобы сортируемый массив разбивался на две примерно равные части.

На рис.7.11 показаны шаги выполнения процедуры быстрой сортировки, выполняемые для массива, состоящего из чисел 3,1,4,1,5,9,2,6,5,3. На каждом шаге значение v выбирается как наибольшее значение из двух самых левых различных элементов части текущей части массива. Сортировка завершается, когда части массива, на которые разбивается исходный массив в процессе рекурсивных вызовов процедуры, будут содержать одинаковые элементы.

Алгоритм быстрой сортировки представлен блок-схемами на рис.7.12. Реализация алгоритма представлена в листинге 7.9.

Время выполнения алгоритма быстрой сортировки в худшем случае равно O(n²). Однако, в среднем время выполнения алгоритма быстрой сортировки равно O(nlog₂n). Практика применения алгоритма быстрой сортировки показывает, что он более эффективен чем алгоритм пирамидальной сортировки, у которого время выполнения в худшем случае равно O(nlog₂n).

Листинг 7.8

procedure QuickSort(var X:TMas;N:integer);

begin

QS(1,N,X)

end;

procedure QS(i,j:integer);

var pivot:elementtype; {Опорное значение}

pivotindex:integer; {Индекс элемента массива равного pivot}

k:integer; {Начальный индекс группы элементов >= pivot}

begin

pivotindex=findpivot(i,j);

if pivotindex<>0 then {Различные ключи найдены?}

begin

pivot:=X[pivotindex];

k:=partition(i,j,pivot);

QS(i,k-1);

QS(k,j)

end

end; {QS}

function findpivot(i,j:integer):integer;

var firstkey:elementtype; {Значение первого элемента, т.е. X[i]}

k:integer; {Текущий индекс при поиске различных ключей}

begin

firstkey:=X[i];

k:=i+1;

while not((k>j)or(X[k]<>firstkey)) do k:=k+1;

if k>j then return (0) {Различные элементы не найдены}

else if X[k]>firstkey then return(k)

else return(i)

end;

function partition(i,j:integer; pivov:typeelement):integer;

var l,r:integer;

begin

l:=i; r:=j;

while not(l>r) do

begin

SW(X[l],X[r]);

while X[l]<pivot do l:=l+1;

while X[r]>=pivot do r:=r-1;

end;

return(l)

end;

Реализацию процедуры SW см. в листинге 7.3