Page 89 - Bkhargava_-_Grokaem_algoritmy
P. 89
88 Глава 4. Быстрая сортировка
Этот метод работает при любом опорном элементе. Допустим, вместо 33
в качестве опорного был выбран элемент 15.
Оба подмассива состоят из одного элемента, а вы уже умеете сортировать
такие подмассивы. Получается, что вы умеете сортировать массивы из трех
элементов. Это делается так:
1. Выбрать опорный элемент.
2. Разделить массив на два подмассива: элементы, меньшие опорного,
и элементы, большие опорного.
3. Рекурсивно применить быструю сортировку к двум подмассивам.
Как насчет массива из четырех элементов?
[ 3? \ 10 J 1s l 1]
Предположим, опорным снова выбирается элемент 33.
см / 1!; l 1 ] <%> [ J
Левый подмассив состоит из трех элементов. Вы уже знаете, как сортирует
ся массив из трех элементов: нужно рекурсивно применить к нему быструю
сортировку.
www.trk.kg
