Реферат: Быстрые алгоритмы сортировки

4.Змінюємо місцями A[i] і A[j];

Пункти 2-4 повторюємо доти, поки i < j;

У результаті такого зустрічного проходу початок масиву A[1..i] і кінець масиву A[j..n] виявляються розділеними “бар'єром” x: A[k] ( x при k < i, A[k] ( x при k > j , причому на поділ ми затратимо не більш n/2 перестановок. Тепер залишилося проробити ті ж дії з початком і кінцем масиву, тобто застосувати їх рекурсивно.

Таким чином, описана нами процедура Hoare залежить від параметрів k та m - початкового і кінцевого індексів відрізка масиву, який обробляється.

Procedure Swap(i, j : Integer);

Var b : Real;

Begin

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

End;

Procedure Hoare(L, R : Integer);

Var left, right : Integer;

x : Integer;

Begin

If L < R then begin

x := A[(L + R) div 2]; {вибір бар'єра x}

left := L; right := R ;

Repeat {зустрічний прохід}

While A[left] < x do Inc(left); {перегляд уперед}

While A[right] > x do Dec(right); {перегляд назад}

If left <= right then begin

Swap(left, right); {перестановка}

Inc(left); Dec(right);

end

until left > right;

Hoare(L, right); {сортуємо початок}

Hoare(left, R) {сортуємо кінець}

end

End;

Program QuickSort;