Рис. 8.1 Работа процедуры partition. Незакрашенные элементы относятся к уже сформированным кускам, закрашенные ещё не распределены, (а) Начальное состояние массива, начальный и конечный куски пусты. Элемент х = А\р] = 5 используется в качестве граничного, (б) Результат первого прохода цикла while (строки 4-8). (в) Элементы А[г] и A[j] меняются местами (строка 10). (г) Результат второго прохода цикла while, (д) Результат третьего (последнего) прохода цикла while. Поскольку г j, процедура останавливается и возвращает значение q = j. Элементы слева от A[j] (включая сам этот элемент) не больше, чем х = 5, а элементы справа от A[j] не меньше, чем х = 5.

части. Процедура возвращает значение j.

Хотя идея процедуры очень проста, сам алгоритм содержит ряд тонких моментов. Например, не очевидно, что индексы г и j не выходят за границы промежутка [р..г] в процессе работы. Другой пример: важно, что в качестве граничного значения выбирается А\р], а не, скажем, А[г]. В последнем случае может оказаться, что А[г] - самый большой элемент массива, и в конце выполнения процедуры будет г = j = г, так что возвращать q = j будет нельзя - нарушится требование q < г, и процедура Quicksort зациклится. Правильность процедуры Partition составляет предмет задачи 8-1.

Время работы процедуры Partition составляет в (га), где га = г - р + 1 (см. упр. 8.1-3).

Упражнения

8.1-1 Покажите, следуя образцу рис. 8.1, как работает процедура Partition для массива А = (13,19, 9,5,12,8,7,4,11, 2,6,21).

8.1-2 Пусть все элементы массива А\р .. г] равны. Какое значение вернёт процедура Partition?

8.1-3 Приведите простое соображение, объясняющее, почему время работы процедуры Partition составляет в (га).

8.1-4 Как отсортировать массив в порядке убывания (а не возрастания), используя те же методы?

Время работы алгоритма быстрой сортировки зависит от того, как разбивается массив на каждом шаге. Если разбиение происходит на примерно равные части, время работы составляет О (га lgra), как и для сортировки слиянием. Если же размеры частей сильно отличаются, сортировка может занимать время О (га2), как при сортировке вставками.

Наихудшее разбиение

«Наиболее неравные части» получатся, если одна часть содержит га - 1 элемент, а вторая - всего 1. (Как мы увидим в разделе 8.4.1, это наихудший случай с точки зрения времени работы.) Предположим, что на каждом шаге происходит именно так. Поскольку процедура разбиения занимает время в(га), для времени работы Г(га) получаем соотношение

(последняя сумма - арифметическая прогрессия, см. формулу (3.2)). Дерево рекурсии для этого случая показано на рис. 8.2. (По поводу деревьев рекурсии см. разд. 4.2.)

Мы видим, что при максимально несбалансированном разбиении время работы составляет 0(га2), как и для сортировки вставками. В частности, это происходит, если массив изначально отсортирован (заметим, что в этом случае сортировка вставками производится за время в (га)).

Наилучшее разбиение

Если на каждом шаге массив разбивается ровно пополам, быстрая сортировка требует значительно меньше времени. Действительно, в этом случае рекуррентное соотношение имеет вид

и, согласно теореме 4.1 (случай 2), Т(п) = O(ralgra). Дерево рекурсии для этого случая показано на рисунке 8.3.

8.2. Работа быстрой сортировки

Поскольку Т(1)

Г(га) = Г(га - 1) +6(га) 0(1), имеем

Т(п) = Т(п

Т(п) = 2Г(га/2) + 0(га)

Рис. 8.2 Дерево рекурсии процедуры quicksort для наихудшего случая (процедура partition каждый раз производит разбиение, в котором одна из частей содержит один элемент). Время работы равно 0(п ).

Рис. 8.3 Дерево рекурсии процедуры quicksort для наилучшего случая (массив каждый раз разбивается пополам). Время работы равно 0(nlgn).

Промежуточный случай

Как будет показано в разделе 8.4, среднее время работы (с точностью до множителя) совпадает с временем работы в наилучшем случае. Чтобы объяснить это, посмотрим, как меняется рекуррентное соотношение в зависимости от степени сбалансированности разбиения.

Пусть, например, на каждом шаге массив разбивается на две части с отношением размеров 9:1. Тогда

ТЫ) = Т(9га/10) + Т(п/Щ + п

(для удобства мы заменили в (га) на га). Дерево рекурсии показано на рисунке 8.4. На каждом уровне мы производим не более га действий, так что время работы определяется глубиной рекурсии.