Быстрая сортировка

Относится к методам обменной сортировки. В основе лежит методика разделения ключей по отношению к выбранному.

Слева от 6 располагают все ключи с меньшими, а справа - с большими или равными 6.

Sub Sort (L, R)

i = L

j = R

x = a((L + R) div 2)

repeat

while a(i) < x do

i = i + 1

endwhile

while a(j) > x do

j = j - 1

endwhile

if i <= j then

y = a(i)

a(i) = a(j)

a(j) = y

i = i + 1

j = j - 1

endif

until i > j

if L < j then

sort (L, j)

endif

if i < R then

sort (i, R)

endif

return

Sub QuickSort

Sort (1, n)

return

Эффективность алгоритмаQuick Sort

Из всех существующих методов сортировки Quick Sort самый эффективный.

Его эффективность имеет порядок О (n log2 n)