Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 19
Текст из файла (страница 19)
Как мы видим, быстрая сортировка напоминает азартн)ю игру, где следует заранее рассчитать, сколько можно позволить себе проиграть в случае невезения. Из этого нужно сделать важный вывод, на который программист должен обратить особое внимание. К чему приводит наихудший случай, разобранный выше в связи со скоростью выполнения про>раммы 2,11? Мы видим, что при каждом разбиении правая часть подмассива состоит из одного элемента; запрос на сортировку этой части заносится в стек для последуюшего выполнения. Следовательно, максимальное число запросов и поэтому необходимый общий размер стека оказываются равными п.
Конечно >ке, это абсолютно неприемлемо. (Заметим, что с рекурсивной версией дело обстоит не лучше, а на самом деле даже хуже, поскольку система, допускающая рекурсивный вызов процедур, должна автоматически сохранять значения локальных переменных и царамет. ров при всех вызовах процедур, и для этой ьелн она использует неявный стек.) Это можно исправить, если хранить з стеке запрос на сортировку более длинной части и сразу продолжать дальнейшее разделение коротких частей.
В этом случае размер стека можно ограннчить до ш = = 1ойтп. в.2. Сортировка массивов гоз 1(еобходимое изменение программы 2.11 касается лишь части, фиксврующей новые запросы. Она теперь имеет вид К1 — 1 < г-г (Ъен Ъей)п 11 ( < г ЪЪеп Ъей)п [записи запроса на сортировку правой части) в:= в+1; в(иск[в) .1:= (; в(аск[4 .г:- г епй; г:= у' [продолжение сортировки левой части) спи е1зе Ьейш Ы 1 < ( гйеп Ъея)п [запись в стек запроса на сортировку левой части1 в г в+1; в(асй[в) .1: ° )т в(асйгв),г г 1 епй; [ продолжение сортировки правой части'1 епй (2.16) .2.2.1. Поиск медианы Меднавой последовательности из п элементов называется элемент, значение которого меньше (илн равно) половины п элементов н больше (нли равно) другой половины.
Например, медиана 16 12 99 95 18 87 10 1) а[8) <х для всех Iг <г, 2) а[6) ьх для всех Й >(, 3) (>). (2.1?) есть 18. Задачу поиска медианы принято связывать с сортировкой, так как меднану всегда можно найти следующим способомг рассортировать п элементов и затем выбрать средний элемент, Но разделение, которое выполняет программа 2.9, позволяет потенциально найти медиану значительно быстрее. Рассматриваемый здесь метод дает возможность решать н более общую задачу поиска элемента с Ъ-м по величине значением нз и элементов. Поиск медианы является частным случаем для (( = п/2. Алгоритм, изобретенный К.
Хоором [2.4), работает следующим образом. Прежде всего применяется операция разделения, нспользуемая прн быстрой сортировке, с 1 = 1, г = п и с а [й), выоранным в качестве разделяющего значения (граннцы) х. Получаются значения индексов г' и ), такие, что 2. Сортировка 104 Возможны три варианта: 1. Разделяющее значение х было слишком мало; в результате граница между двумя частями ниже искомого зиачеиия й. Процесс разбиения следует повторить для злемеитов а Д...., а 1г) (см. рис. 2.9). / у г Рис. 2.9. Гранина слишком низко.
2. Выбранная граница х была слишком велика. Операцию разбиения следует повторить иа подмассиве а [1), ..., а Ц (см. рис. 2.10). ! г г Рис 2,10, Гранина слишком высоко. 3, Звачение А лежит в интервале 1 < я ( й злемеит а [Ц разделяет массив в заданной пропорции и, следовательно, является искомым (см. рис.
2 11). уяг Рис. 2Л1. Гранина проведена правильно, Процесс разбиения повторяется до появления случая 3. Этой итерации соответствует следующий фрагмент программы: 1:= 1; г1= я1 ттв11е 1 < и яо Ьей(и х:= а(Ц1 рлгг(г(оп(а(1)... а(г)) ° (2.18) Ы1 < Й айеи 1;= 1; Ый < уйеи г:=у За формальным доказательством корректиости зтого алга- ритма мы отсылаем читателя к статье Хоора. Теперь мы можем целиком иаписать всю программу г(пд.
2.2. Сортировка массивов ргесейвгейпг((1с; 1«гвйвг); тае 1гРДЯн,х1 1нгейег; Ъей(а 1:и 1; г:= н1 нЫ!е1< ге« Ьефа х:= «Я; 1; 1; 1: = г; тЕрааФ (Вр(гт) нЬ11е «Я < х де г';= г+1; нЬИе х < «И йе 1:= 1' — 1; Ы 1 ~,.1 тйеа Ъей)а эв: «(1); аЯ: «(Я; «(Я: ==-.
гв1 1: г+1;1:= 1 — 1 еай вв111 1 >,/; 111 < 1с 1Ьеа 1:= г; 11 1с < г 1Ьеа г:== г' евй еай (.би 1) Программа 2Л2. Полек в-го элемента. Если предположить, что в среднем каждое разбиение умень- шает вдвое размер подмассива, в котором содержится иско- мый элемент, то число необходимых сравнений равно 2+4 '''+ (2.19) т. с. порядка и. Этим обьяспяется эффективность программы гггнг( при нахождении медиан н других квантилей и ее преимушество по сравнению с приходящим вначале в голову методом сортировки всего мнохгсства элементов для выбора )г-го по величине (такой метод в лучшем случае дает порядок п.)од«). Однако в худшем случае каждын шаг разбиения уменьшает размер множества, в котором ищется нужный элемент, только на 1, и поэтому требуется порядок пэ сравне.
иий. Следовательно, этот алгоритм тоже вряд ли стогга использовать для небольшого числа элементов (скажем, меньше 10). 2.2.8. Сравнение методов сортировки массивов В завершение нашего обзора методов сортировки мы попытаемся сравнить их эффективность. Пусть и по-прежнему обозначает число сортируемых элементов, а С и М вЂ” соответственно количество необходимых сравнений клгочей и 2.
Сорытровка 105 пересылок элементов. Для всех трех простых методов сортировки можно дать замкнутые аналитические формулы. Они приведены в табл. 2.8. Заголовки столбцов М!п, Мах, Среди. определяют соответственно минимумы, максимумы н ожидаемые средние значения для всех л) перестановок и элементов. Таблица 2.8. Сравнение простых методов сортировки средн Мхх хт!и С=л — 1 (а'+ а — 2)/4 (ае — а)/2 — 1 М = 2 (л — 1) (и' — эл — !О)/4 (а-'+ За — 4),'2 Простые. вкхючеиия (их — и)/2 а (1п л+ 0,57) (ах — а)/2 а'/4 + 3 (л — 1) С = (ат — л)/2 М = 3 (л — 1) Простой выбор С (а' — и)/2 М 0 (лт — и)/2 (а' — и) * 0,75 (а' — л)/2 (л' — л) 1,5 Простоя обмен (метод пузырька) Для усовершенствованных методов нет достаточно простых и точных формул, Йсе, что можно сказать,— зто что стоимость вычислений равна с; лпа в случае сортировки Шелла и с; и !од п в случаях пирамидальной н быстрой сортировок.
Эти формулы дают лишь приблизительную оценку эффективности как функции от и; онн допускают классифнкацяю алгоритмов сортировки на простые (л') и усовершенствованные, или «логарифмические» (и 1ояи). Однако для практических целей полезно иметь некоторые экспериментальные данные, которые могут пролить свет на коэффициенты ги позволяющие проводить дальнейшую оценку различных методов.
Кроме того, в этих формулах не учитываются затраты на другие операции, отличные от сравнений ключей и пересылок элементов, такие, как управление циклами и т. д. !Разумеется, эти факторы в какой-то степени завксят от конкретных систем, ко тем не менее некоторый пример эксперимен. тально полученных данных является информативным. В табл. 2.9 приведено время (в миллисекундах), которое затратила система Паскаль на вычислительной машине С()С б400 иа выполнение сортировки описанными здесь методами. В трех столбцах указано время, потребовавшееся для сортировки уже рассортированного массива, случайной персстановки и массива с обратным порядком элементов. Левое 2.2. Сортировка массивов 107 таолнца 2.9. Время выполнения программ сортяровкн Случаанма массне Унорндочснюаа в обратном варнаке массне УноеаДочсннма массне Простое включение Бинарное включение Простой выбор Метод пузырька Метод пузырька с ограничением Шеакер.сортировка Сортировка Шелла Пирамидальная сортировка Быстрая сортировка Сортировка слвяниемч) 12 23 56 125 489 1907 540 2!65 366 !444 373 1327 509 1956 !026 4054 704 2836 662 2490 695 2675 1492 5931 5 8 5 9 58 116 1104 4270 96! 3642 127 349 1645 6542 1619 6520 157 492 1!6 253 31 69 99 234 110 241 60 146 !02 242 104 226 37 79 99 232 ч см.
Равд. тзл число в каждой колонке дано для массива из 256 элементов, а правое — для 512 элементов. Эти данные демонстрируют явное отличие методов пз от методов л 1он л. Примечательны следующие моменты: 1. Преимущество сортировки бинарными включениями по сравнению с сортировкой простыми включениями действительно ничтожно, а в случае уже имекнцегося порядка вообще отсутствует. 2.
Сертировка методом пузырька определенно является наихудшей среди всех сравниваемых методов. Ее улучшенная версия — шейкер-сортировка все-таки хуже, чем сорти. ровка простыми включениями и простым выбором (кроме патологического случая сортировки уже рассортированного массива). 3, Быстрая сортировка превосходит пирамидальную сортировку в отношении 2 к 3. Она сортирует массив с элементами, расположенными в обратном порядке практически так же, как уже рассортированный. Следует добавить, что этн данные были получены при сортировке элементов, состоящих только из ключа без сопутствующей информации. Это — не слишком реалистичное допущение; в табл.
230 показано, как влияет увеличение размера элементов на скорость работы программ. В выбранном примере сопутствующие данные занимают в 7 раз больше памяти, чем ключ, Левое число в каждой колонке показывает время, нужное для сортировки записей без сопутствующих 1О8 2. Сортировка тнблнцв 2.Ш. Время выполнения программ сортировки !Ключи с сопутствующей информацией) унорядоченныа в обратном паряняе массив Упорядоченныа массив ела чван ыа массив Простые включения Бинарные включения Простой выбор Метод пузырька Метод пузырька с ограничением Шейкер-сортировка Сортировка Шелла Пирамидальная сортировка Быстрая сортировка Сортировка слиянием* 704 2150 662 2070 695 1430 402 5599 12 46 56 76 489 547 540 6!О Збб 1129 373 1105 509 607 !026 32!2 5 5 5 5 58 186 ! 104 3237 96! 307! !27 373 1645 5762 16!9 5757 !57 433 !16 264 31 55 99 196 110 246 60 !37 102 195 104 227 37 75 99 !87 * с».
раап. аа~ данных, правое — отражает сортировку с сопутствующями данными; п = 256. Обратите внимание на следующие детали: ). Сортировка простым выбором дает существенный выигрыш и оказывается лучшим из простых методов. 2. Сортировка методом пузырька по-прежнему является наихудшим методом (она еще больше сдала свои позиции!), и лишь ее «усовершенствование», называемое шейкерсортировкой, еше чуть хуже в случае массива с обратным порядком, 3. Быстрая сортировка даже укрепила свою позицию в качестве самого быстрого метода и оказалась действительно лучшим алгоритмом сортировки. 2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
