Для быстрой сортировки мы хотим получить оценку медианы, чтобы решить, как проводить процедуру разделения. Свойство этого алгоритма заключается в том, что нам не нужна особо точная оценка (мы вообще можем обойтись без такой оценки, если стоимость ее вычисления высока); мы просто хотим избежать исключительно плохой оценки. Если используется случайная выборка из одного элемента, получается рандомизированный алгоритм, который виртуально обладает высоким быстродействием, независимо от природы входных данных. Если произвести случайную выборку из файла из трех или из пяти элементов, а затем воспользоваться медианой из этой выборки в процедуре разделения, получится лучшее разбиение, но такое усовершенствование достигается ценой выполнения выборки.

Программа 7.4. Улучшенная быарая сортировка

Выбор медианы из первого, среднего и концевого элементов в качестве разделяющего элемента и отсечение рекурсии меньших подфайлов может привести к существенному повышению эффективности быстрой сортировки. Данная реализация осуществляет разделение по медиане из первого, среднего и концевого элементов массива (не следует использовать эти элементы в процессе разделения для других целей). Файлы длиной 11 и меньше в процессе разделения игнорируются; затем для окончания сортировки используется команда insertion из главы 6.

static const int М = 10; template <class Item>

void quidcksort (Item a[], int 1, int r)

if (r-l <= M) return; exch(a[(l+r)/2] , a[r-l]); comexch(a[l], a[r-l]); comexch(a[1] , a[r]); comexch(a[r-l] , a[r]); int i = partition (a, 1+1, r-l) ; quidcksort(a, 1, i-1); quidcksort(a, i+1, r);

template <class Item>

void hybridsort(Item a[], int 1, int r)

{ quidcksort(a, 1, r) ; insertion(a, 1, r) ; }

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

Таблица 7.1. Эмпирическое исследование алгоритмов быстрой сортировки

Быстрая сортировка (программа 7.1) работает примерно в два раза быстрее, чем сортировка методом Шелла (программа 6.6). Совершенствование метода отсечения меньших подфайлов и метода медианы из трех элементов (программа 7.4) сокращают время выполнения сортировки примерно на 10 процентов каждое.

Упражнения

7.28. Наша реализация метода медианы из трех элементов тшательно следит за тем, чтобы элементы, составляюшие выборку, не принимали участия в процессе разделения. Одна из причин заключается в том, что они могут быть использованы в качестве служебных меток. Назовите другие причины.

7.29. Реализовать быструю сортировку на базе разделения по медиане случайной выборки из файла, содержащей пять элементов. Элементы выборочной совокупности не должны принимать участия в разделении (см. упражнение 7.28). Сравните эффективность вашего алгоритма с эффективностью метода медианы из трех элементов на примерах крупных файлов с произвольной организацией.

7.30. Выполните программу из упражнения 7.29 на крупных файлах со специальной организацией - например, отсортированные файлы, файлы, упорядоченные в обратном порядке или файлы с одинаковыми ключами элементов. Насколько ее эффективность при сортировке указанных файлов отличается от эффективности, полученной для файлов с произвольной организацией?

7.31. Реализовать быструю сортировку с использованием выборочных совокупностей размером 2 - \. Сначала выполнить сортировку выборочной совокупности, затем выполнить рекурсивную программу, осуществляющую разделение с использованием медианы из элементов выборочной совокупности, и поместить обе половины оставшейся части выборочной совокупности в каждый подфайл таким образом, чтобы они могли быть использованы в этих подфайлах без дальнейшей сортировки. Такой метод сортировки называется сортировкой методом случайной выборки {samplesort).

7.32. Выполнить эмпирические исследования, чтобы определить наилучший размер выборочной совокупности для сортировки методом случайной выборки (см. упражнение 7.31) для 7V = 10 10 *, 10 и 10. Имеет ли значение, какой вид сортировки используется для упорядочения выборочной совокупности: быстрая сортировка или сортировка методом случайной выборки (samplesort)?

7.33. Показать, что если внести изменения в программу 7.4, предусматривающие исключение первой операции обмена и пропуск ключей, равных разделяющему элементу, то время выполнения сортировки файла, организованного в обратном порядке, находится в квадратичной зависимости от длины файла.

7.6. Дублированные ключи

Файлы с большим числом дублированных сортируемых ключей довольно часто встречаются в различных приложениях. Например, может потребоваться сортировка большого файла с персональными данными по году рождения или, скажем, сортировка для деления персонала по половому признаку.

Когда в сортируемом файле имеется множество дублированных ключей, нельзя со всей определенностью утверждать, что рассмотренные нами различные реализации быстрой сортировки показывают недопустимо низкую эффективность, однако их можно существенно улучшить. Например файл, который состоит исключительно из равных один другому ключей (одно и то же значение), вовсе не нуждается в дальнейшей сортировке, однако наши реализации продолжают процесс разделения, подвергая обработке все более мелкие подфайлы независимо от того, насколь большим является исходный файл (см. упражнение 7.8). В ситуации, когда во входном файле присутствует большое число дублированных ключей, рекурсивная природа быстрой сортировки приводит в тому, что подфайлы, содержащие только элементы с одним и тем же ключом, встречаются довольно часто, благодаря чему существуют большие потенциальные возможности для совершенствования алгоритма сортировки.

Одйа достаточно простая идея заключается в делении файла на три части, одна - для ключей, меньших разделяющего элемента, другая - для ключей, равных ему, и третья - для ключей, больших разделяющего элемента:

меньше чем v

больше чем v

равные V

t Г 1 t

1 j i г

Выполнение такого разбиения намного сложнее, чем разбиение на две части, которым мы пользовались ранее. Были предложены различные методы решения этой задачи. Классическим упражнением по программированию, получившим широкую известность с легкой руки Дейкстры (Dijkstra), стала Задача голландского национального флага, и прежде всего из-за того, что три возможных категорий ключей могут соответствовать трем цветам флага (Dutch National Flag problem) {см. раздел ссылок). В рамках быстрой сортировки мы добавляем еще одно ограничение заключающееся в том, что эта задача должна быть решена за один проход по файлу - алгоритм, который предусматривает два прохода по данным, замедлит быструю сортировку в два раза, даже если в исходном файле вообще не будет дублированных ключей.

Оригинальный метод, предложенный Бентли (Bentley) и Макилроем (МсПгоу) в 1993 г. для разбиения файла на три части, представляет собой модификацию стандартной схемы разделения и предусматривает следующее: ключи, равные разделяющему элементу и встретившиеся в левом подфайле, накапливаются в левом конце файла, ключи, равные разделяющему элементу и встретившиеся в правом подфайле, накапливаются в правом конце файла. Во время выполнения процесса разделения мы придерживаемся следующей схемы: