ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

swap ( A[lo], A[hi] );

goto 1

end;

k := lo + 1; j := hi;

v := A[lo]; {?!}

while ( k < j ) do

if A[k] < v then k := k + 1

else

begin

if A[j] < v then swap ( A[k], A[j] );

j := j - 1

end;

{ k = j }

if A[k] >= v then k := k - 1;

{ A[k] є останнім від початку елементом, }

{ значення якого менше v }

swap ( A[lo], A[k] ); { A[k] = v }

quicksort ( A , lo, k - 1 );

quicksort ( A , k + 1, hi );

1: end

Якщо за виконання кожного виклику після циклу while значення змінної k приблизно рівне (lo+hi)/2, то складність швидкого сортування масиву з n елементів можна оцінити як O(nlogn). Середня кількість порівнянь елементів усіх можливих числових послідовностей довжини n також має оцінку O(nlogn); доведення є, наприклад, у книзі [АХУ]. Емпіричні дослідження свідчать, що швидке сортування вимагає в середньому елементарних дій приблизно вдвічі менше, ніж сортування деревом, і вчетверо менше, ніж сортування злиттям. Але якщо початковий масив близький до відсортованого, то його сортування за наведеним алгоритмом вимагає вже O(n2) порівнянь. У такому випадку відокремлюючим елементом не можна вибирати значення A[lo].

Існує багато способів вибору іншого відокремлюючого значення. Наприклад, можна вибрати значення елемента з випадковим номером серед номерів lo, … , hi, або середнє із значень A[lo], A[hi], та A[(lo+hi)div2]. У такому разі перед оператором процедури