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

If i <= n div 2 then begin

SortTree(2*i); SortTree(2*i+1); Conflict(i, n)

end

end;

На II-ом етапі - етапі просівання - для k від n до 2 повторюються наступні дії:

1.Переставити A[1] і A[k];

2.Побудувати сортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду в корені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.

Program HeapSort;

Const n = 100;

Var A : Array[1..n] of real;

k : Integer;

{процедури ConSwap, Conflict, SortTree, введення, виведення}

Begin

{ введення }

SortTree(1);

For k := n downto 2 do begin

ConSwap(k, 1); Conflict(1, k - 1)

end;

{ виведення }

End.

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

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

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

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

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

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

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

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