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

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;

Const n = 100;

Var A : array[1..n] of Integer;

{ процедури Swap, Hoare, введення і висновку }

Begin

Inp; Hoare(1, n); Out

End.

Аналіз складності алгоритму в середньому, що використовує гіпотезу про рівну імовірність усіх входів, показує, що:

C(n) = O(n log2 n), M(n) = O(n log2 n)

У гіршому випадку, коли в якості бар'єрного вибирається, наприклад, максимальний елемент підмассиву, складність алгоритму квадратична.

1.4 Метод цифрового сортування

:

\x00BA

P

.

\x7500\x0108\x2400.

0

2

6

8

: