в. Измените процедуру Quicksort так, чтобы объём стека не превышал в (lgra) (сохраняя оценку O(ralgra) для среднего времени работы).

8-5 Разбиение с помощью медианы трёх элементов

Работу процедуры Randomized-Quicksort можно ускорить, выбирая граничный элемент для разбиения более тщательно. Один из распространённых подходов - это метод медианы трёх (median-of-3 method): в качестве граничного элемента используется средний из трёх случайно выбранных элементов массива. Мы будем предполагать, что все элементы входного массива А[1..га] различны и га 3. Через А[1..га] будем обозначать отсортированный массив (который мы и хотим получить). Пусть pi = Р{ж = А[г]}, где х - граничный элемент, выбранный описанным выше способом.

а.Выразите вероятность рг- (для г = 2, 3,..., га - 1) через inn (заметьте, что р\ = рп = 0).

б.Насколько вероятность выбрать средний элемент (А[[(га + 1)/2J]) больше, чем при обычном случайном выборе? К чему стремится отношение этих вероятностей при га -> оо?

в.Будем называть разбиение с граничным элементом х «хорошим», если х = A[i], где га/3 г 2га/3. Насколько вероятность «хорошего» разбиения больше, чем при обычном случайном выборе? (Указание: при вычислениях оцените сумму интегралом.)

г.Докажите, что использование метода медианы трёх сохраняет оценку fi(ralgra) для времени работы быстрой сортировки (и влияет лишь на константу перед га lgra).

Замечания

Алгоритм быстрой сортировки принадлежит Хоару [98]. В статье Седжвика [174] обсуждаются детали реализации быстрой сортировки и их влияние на время работы. Вероятностные алгоритмы для разных задач рассматриваются в статье Рабина [165].

9

Сортировка за линейное время

Мы познакомились с различными алгоритмами, которые могут отсортировать га чисел за время О (га lgra). Алгоритмы сортировки слиянием (merge sort) и сортировки с помощью кучи (heap sort) работают за такое время в худшем случае, а у алгоритма быстрой сортировки таковым является среднее время работы. Оценка О (га lgra) точна: для каждого из этих алгоритмов можно предъявить последовательность из га чисел, время обработки которой будет Q(гаlgra).

Все упомянутые алгоритмы проводят сортировку, основываясь исключительно на попарных сравнениях элементов, поэтому их иногда называют сортировками сравнением (comparison sort). В разделе 9.1 мы покажем, что всякий алгоритм такого типа сортирует га элементов за время не меньше fi(ralgra) в худшем случае. Тем самым алгоритмы сортировки слиянием и с помощью кучи асимптотически оптимальны: не существует алгоритма сортировки сравнением, который превосходил бы указанные алгоритмы более, чем в конечное число раз.

В разделах 9.2, 9.3 и 9.4 мы рассматриваем три алгоритма сортировки (сортировка подсчётом, цифровая сортировка и сортировка вычерпыванием), работающих за линейное время. Разумеется, они улучшают оценку fi(ralgra) за счёт того, что используют не только попарные сравнения, но и внутреннюю структуру сортируемых объектов.

9.1. Нижние оценки для сортировки

Говорят, что алгоритм сортировки основан на сравнениях, если он никак не использует внутреннюю структуру сортируемых элементов, а лишь сравнивает их и после некоторого числа сравнений выдаёт ответ (указывающий истинный порядок элементов). Так мы приходим к модели алгоритмов сортировки, называемой разрешающими деревьями.

Рис. 9.1 Разрешающее дерево для алгоритма сортировки вставками, обрабатывающего последовательность из трёх элементов. Поскольку число перестановок из трёх элементов равно 3! = 6, у дерева должно быть не менее 6 листьев.

Разрешающие деревья

Начнём с примера: на рис. 9.1 изображено разрешающее дерево

(decision tree), соответствующее сортировке последовательности из трёх элементов с помощью алгоритма сортировки вставками из раздела 1.1.

Пусть теперь мы сортируем га элементов а\,..., ап. Каждая внутренняя вершина разрешающего дерева соответствует операции сравнения и снабжена пометкой вида аг- : cij, указывающей, какие элементы надо сравнить (1 i,j га). Каждый лист разрешающего дерева снабжен пометкой (тг(1), 7г(2),..., тг(га)), где ж - перестановка га элементов (см. разд. 6.1 по поводу перестановок). Для получения нижних оценок мы можем ограничиться случаем различных элементов, тогда результатом сортировки будет перестановка элементов в порядке возрастания.

Опишем, какой алгоритм сортировки соответствует данному разрешающему дереву. Надо пройти по дереву от корня до листа. Выбор направления (налево или направо) происходит так. Пусть в вершине написано аг- : cij. Тогда надо идти налево, если аг- cij, и направо в противном случае. Если в листе, в который мы в итоге приходим, записана перестановка тг, то результатом сортировки считаем последовательность аж, civ2), , аж{п) которая должна быть неубывающей, если алгоритм правилен.

Каждая из га! перестановок должна появиться хотя бы на одном листе разрешающего дерева (поскольку правильный алгоритм должен предусматривать все возможные порядки).

Нижняя оценка для худшего случая

Число сравнений в худшем случае для такого алгоритма равно высоте разрешающего дерева - максимальной длине пути в этом дереве от корня до листа. Следующая теорема дает нижнюю оценку на эту высоту.