1.21. Проведите эмпирические исследования с целью определения среднего размера стека, используемого при быстрой сортировке с отсечением подфайлов с размерами, не превышающими Л/, для сортировки файла с произвольной организацией, состоящего из элементов, причем Л/ = 10, 100 и 1000 и Л=10 , 10\ 10 и 10

7.5 Метод разделения с вычислением медианы из трех элементов

Еще одно усовершенствование метода быстрой сортировки заключается в использовании такого разделяющего элемента, который с достаточно большой вероятностью делил бы файл вблизи его середины. Наиболее безопасный выбор, минимизирующий вероятность возникновения наихудшего случая, состоит в использовании в качестве разделяющего элемента случайного элемента массива. Тогда вероятность возникновения наихудшего случая становится ничтожно малой. Этот метод представляет собой пример вероятностного алгоритма {probabilistic algorithm) - такого алгоритма, который использует случайный характер величин для достижения высокой эффективности с большой вероятностью, независимо от степени упорядоченности входных данных. Далее в этой книге мы столкнемся с многочисленными примерами использования свойства случайности при разработке структуры алгоритмов, в частности, когда предполагается наличие той или иной тенденции во входных данных. На практике использование в рамках быстрой сортировки генератора случайных чисел с этой целью может оказаться излишним: простой произвольный выбор оказывается достаточно эффективным.

Другой хорошо известный способ нахождения подходящего разделяющего элемента заключается в том, что производится выборка трех элементов из файла, затем в качестве разделяющего элемента используется медиана из этих трех элементов. Выбирая для такой цели три элемента из левой части, из середины и из правой части массива, можно также включить в эту схему служебные метки: сначала сортируем три выбранных элемента (с использованием метода трех обменов, описанного в главе 6), затем меняем местами элемент из середины с элементом а[г-1], далее выполняем алгоритм разделения на элементах а[1+1],...а[г-2]. Приведенное усовершенствование получило название метода медианы из трех элементов {median-of-three).

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

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

сортировки на 20-25 процентов. Профамма 7.4 представляет собой реализацию, в которой применены все упомянутые усовершенствования.

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

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

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

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

РИСУНОК 7.10. РАЗМЕРЫ СТЕКОВ ДЛЯ УЛУЧШЕННЫХ ВАРИАНТОВ БЫСТРОЙ СОРТИРОВКИ

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

mmm mm m

РИСУНОК 7.11. ДИНАМИЧЕСКИЕ ХАРАКТЕРИСТИКИ БЫСТРОЙ СОРТИРОВКИ С ВЫЧИСЛЕНИЕМ МЕДИАНЫ ИЗ ТРЕХ ЭЛЕМЕНТОВ НА ФАЙЛАХ РАЗЛИЧНЫХ ТИПОВ.

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