Упражнения

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

6.75. Предположим, что используется сортировка вставками для упорядочения случайно распределенного файла, элементы которого принимают одно из трех возможных значений. Какой зависимости подчиняется время выполнения сортировки: линейной, квадратичной или некоторой промежуточной зависимости?

о 6.76. Показать, как файл ABRACADABRA сортируется при помощи метода распределяющего подсчета.

6.77. Реализовать сортировку методом распределяющего подсчета элементов, которые представляют собой потенциально большие записи с целочисленными ключами, принимающими значения в небольшом диапазоне.

6.78. Реализовать сортировку методом распределяющего подсчета в виде сортировки по указателям.

Быстрая сортировка

мой настоящей главы является алгоритм сортировки,

который, по-видимому, используется гораздо чаще любого другого, а именно - алгоритму быстрой сортировки (quicksort). Базовый алгоритм этого вида сортировки был открыт в 1960 г. Хоаром (C.A.R.Hoare), и с той поры многие специалисты посчитали своим долгом досконально изучить его (см. раздел ссылок). Быстрая сортировка стала популярной прежде всего потому, что ее нетрудно реализовать, она хорощо работает на различных видах входных данных и во многих случаях требует меньще затрат ресурсов по сравнению с другими методами сортировки.

Алгоритм быстрой сортировки обладает и другими весьма привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного стека), на выполнение сортировки 7V элементов в среднем затрачивается время, пропорциональное 7V log УУ и для него характерны исключительно короткие внутренний циклы. Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется операций, он хрупок в том смысле, что даже простая ошибка в реализации может пройти незамеченной и вызвать ошибки в работе алгоритма на некоторых видах файлов.

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

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

Заманчиво попытаться разработать способы улучшения быстрой сортировки: чем выше быстродействие алгоритма сортировки, тем привлекательнее выглядят возможности вычислительных систем, а быстрая сортировка представляет собой почтенный метод, который лишь усиливает это впечатление. Практически с момента опубликования Хоаром алгоритма быстрой сортировки в литературе стали регулярно появляться его усовершенствованные версии. Предлагалось и анализировалось множество идей, но при этом совсем не трудно ошибиться при оценке этих улучшений, поскольку данный алгоритм настоль хорошо сбалансирован, что эффект от усовершенствования одной части программы может послужить причиной ухудшения функционирования другой ее части. Мы детально изучим три модификации, которые сушественно повышают эффективность быстрой сортировки.

Тшательно сбалансированная версия быстрой сортировки, по всей вероятности, будет выполняться быстрее любого другого метода сортировки на большинстве компьютеров, к тому же быстрая сортировка широко используется как библиотечная профамма сортировки и для других серьезных приложений сортировки. В самом деле, сортировка из стандартной библиотеки С++ называется qsort (б[ысфая] сортировка), ибо обычно именно алгоритм быстрой сортировки лежит в основе различных реализаций. Однако, время выполнения быстрой сортировки зависит от организации входных данных и колеблется между линейной и квадратичной зависимостью от количества сортируемых элементов и пользователи иногда бывают неприятно удивлены неожиданно неудовлетворительными, неприемлемыми результатами сортировки некоторых видов входных данных, особенно когда используются хорошо отлаженные версии этого алгоритма. Если приложение работает настолько плохо, что возникает подозрение в наличии дефектов в реализации быстрой сортировки, то сортировка методом Шелла может оказаться более удачным выбором, обеспечивающим лучший результат при меньших затратах на реализацию. Следует отметить, что в случае особо крупных файлов быстрая сортировка выполняется примерно в пять-десять раз быстрее сортировки методом Шелла, при этом на некоторых видах файлов, довольно часто встречающихся на практике, может быть достигнута еще большая эффективность данного вида сортировки.

7.1. Базовый алгоритм

Быстрый метод сортировки функционирует по принципу разделяй и властвуй . Он делит сортируемый массив на две части, затем сортирует эти части независимо друг от друга. Как. будет показано далее, точное положение точки деления зависит от исходного порядка элементов во входном файле. Суть метода заключается в процессе разбиения файла, который переупорядочивает файл таким образом, что выполняются следующие условия: