Page 91 - Bkhargava_-_Grokaem_algoritmy

90 Глава 4. Быстрая сортировка

Все эти подмассивы содержат от О до 4 элементов. А вы уже знаете, как
отсортировать массив, содержащий от О до 4 элементов, с использовани­
ем быстрой сортировки! Таким образом, независимо от выбора опорного
элемента вы можете рекурсивно вызывать быструю сортировку для двух

подмассивов .
Например, предположим, что в качестве опорного выбирается элемент 3.
Вы применяете быструю сортировку к подмассивам.

1' s,A: (Г 2 \ i]) ~ itSo.t([ill])

-1t
[1 }2]~ (ill]

i

Подмассивы отсортированы, и теперь из них можно собрать отсортирован­
ный массив. Решение работает даже в том случае, если выбрать в качестве
опорного элемент 5:

~So"i: ~ 3\2\1\4 О Ф '\ yt([])
50
~

[1\2\з\4 J 4> [ J

~

www.trk.kg