Швидкі алгоритми сортування, Детальна інформація

End.



Нескладно підрахувати, що С(n) = O( n log2 n ), М(n) = O( n log2 n )

1.3 Швидке сортування Хоара

Удосконаливши метод сортування, який грунтується на обмінах, К. Хоар запропонував алгоритм QuickSort сортування масивів, що дає на практиці відмінні результати і дуже просто програмується. Автор назвав свій алгоритм швидким сортуванням.

Ідея К. Хоара полягає в наступному:

1 Виберемо деякий елемент x масиву A випадковим образом;

2.Переглядаємо масив у прямому напрямку (i = 1, 2,...), шукаючи

в ньому елемент A[i] не менший за x;

3.Переглядаємо масив у зворотньому напрямку (j = n, n-1,..),

шукаючи в ньому елемент A[j] не більший за x;

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); {перегляд назад}