AOP_Tom3 (1021738), страница 102
Текст из файла (страница 102)
Но, наверное, было бы куда спокойнее, если бы мы не знали столько различных подходов к решению данной задачи! Изучение всех этих методов было приятным времяпрепровождением. Но теперь перед нами безрадостная перспектива — предстоит на деле решить, какой метод следует использовать в той или иной конкретной ситуации. Было бы прекрасно, если бы один или два метода сортировки превосходили все остальные безотносительно к приложению или используемой машине. На самом же деле каждый метод имеет свои собственные, одному ему присущие достоинства.
Например, метод пузырька (алгоритм 5.2.2В) не имеет ярко выраженных преимуществ, так как всегда можно найти лучший способ сделать то, что он делает; но даже он после соответствующего обобщения оказывается полезным для сортировки с двумя лентами (см. раздел 5.4.3). Итак, приходим к заключению, что почти все алгоритмы заслуживают того, чтобы о них помнили, так как существуют приложения, в которых какой-либо из них оказывается самым подходящим. В следующем кратком обзоре освещаются основные аспекты наиболее важных алгоритмов внутренней сортировки, с которыми мы встречались. (Как обычно, Х означает число записей в файле.) 1.
Распределяющий подсчет. Если диапазон ключей невелик, очень полезен алгоритм 5.20. Метод устойчив (не изменяет порядок записей с равными клк)чами), но требуется память для счетчиков и 2А' записей. Одна из модификаций, позволяющая сэкономить Х из этих записей ценой усзюйчинсх:ти, встречается в упр. 5.2-.13. 2. Простая вставка. Алгоритм 5.2.15 наиболее прост для программной реализации, пе требует дополнительного объема памяти и довольно эффективен при малых У (скажем, при Х ( 25). Нри больших А' он становится невыносимо медленным, если только исходные данные не окажутся сразу почти упорядоченными. 3.
Сортировка с убывающим смещением. Алгоритм 5.2.1ГУ (метод ГВелла) также довольно просто программируется, использует минимальный обьем памяти и весьма эффективен при умеренно больших!У (скажем, при Х < 1000). 4. Вставка в список. Алгоритм 5.2.!Е основан на той же идее, что и алгоритм простой вставки, и поэтому годится только при небольших ГЕ. Как и в других методах сортировки списков, в нем благодаря операциям со ссылками экономятся затраты на пересылку длинных записей; это особенно удобно, когда записи имеют переменную длину или являются частью других структур данных. 5. Сортировка с вычислением адреса эффективна., если ключи подчиняются известному (обычно — равномерному) закону распределения: важнейшими вариантами этого подхода являются вставки а несколько снискав (программа 5.2.1М) и комбинированная поразрядная сортировка со вставками Мак-Ларена (рассмотренная в конце раздела 5.2.5).
Для погледнего метода достаточно иметь О(~/7х') дополнительных ячеек памяти. Двухпроходный метод, который позволяет иметь дело с неравномерным распределением, анализируется в теореме 5.2.5Т. б. Обменная сортировка са слиянием. Алгоритм 5.2.2М (метод Бэтчера) и родственный ему алгоритм битоннай соргпираеки (упр. 5.3.4-10) полезны, еглн можно одновременно выполнять большое число сравнений. 7.
Обменная сортировка с разделением (метод Хоара, широко известный как быстрая сортировка). Алгоритм 5.2.2Я, вероятно, — самый полезный универсальный алгоритм внутренней сортировки, поскольку ои требует' очень мало памяти и опережает своих конкурентов по среднему времени выполнения на болыпинстве компьютеров. Однако в наихудшем случае он может работать очень медленно.
Поэтому, если вероятность неслучайных данных достаточно велика, приходится тщательно выбирать разделяющие элементы. Если выбирается медиана из трех элементов (как предлагается в упр. 5.2.2-55), то такое поведение, как в наихудшем случае, становится крайне маловероятным и, кроме того, несколько уменьшается среднее время работы. В. Простой выбор. Алгоритм аг.2.35 довольно прост и особенно подходит в случае, когда имеется специальное оборудование для быстрого поиска наименьшего элемента в списке. 9.
Пирамидальная соргаироака. Алгоритм 5.2.3Н при минимальных требованиях к памяти обеспечивает достаточно высокую скорость сортировки; как среднее, так и максимальное время работы примерно вдвое больше среднего времени быстрой сортировки. 10. Слияние списков. Алгоритм 5.2.4В осуществляет сортировку списков, обеспечивая при этом, так же как и алгоритм пирамидальной сортировки, весьма высокую скорость даже в наихудшем случае.
Кроме того, данный метод устойчив по отношению к равным ключам. 11. Поразрядная сортировка с использованием алгоритма 5.2.5Н вЂ” это не что нное, как гортнровка списков, которая приемлема лля клкэчей либо очень коротких, либо имеющих необычный порядок лексикографического сравнения. Вместо ссылок можно применить распределяющий подсчет (п. 1 нашего обзора); такая процедура потребует пространства для 2А' записей и для таблицы счетчиков, но благодаря простоте внутреннего цикла она особенно хороша для сверхбыстрых компьютеров— "пожирателей чисел", имеющих опережающее управление.
(Предостережение. Поразрядную сортировку не следует использовать при малых Х1) 12. Сортировка методам агтаеак и слияния (см. раздел 5.3.1) наиболее приемлема при очень малых Х в "прямолинейных" программах. Например, этот метод оказался бы подходящим в тех приложениях, в которых требуется сортировать много групп из пяти или шести записей. 13. 51огут существовать и гибридные методы, объединяющие один или более из приведенных выше.
Например, короткие подфайлы, возникающие при быстрой сортировке, можно сортировать методом слияния и вставок. 14. И наконец, для реализации безымянного метода, встретившегося в ответе к упр. 5.2.1 — 3, требуется, по-видимому, кратчайшая нз возможных программ сортировки. Но среднее время работы такой программы пропорционально Юз, т. е. это самая медленная программа сортировки из упомянутых в данной книге! Пространственные и временные характеристики многих из этих методов, запрограммированных для компьютера И1Х, сведены в табл. 1.
Важно иметь в виду, что числа в данной таблице являются лишь грубыми оценками относительного времени сортировки. Они применимы только к одному компьютеру, и предположения, касающиеся исходных данных, далеко не для всех программ абсолютно правомерны. Сравнительные таблицы, подобные этой, приводились во многих работах, но не найдется таких двух авторов, которые пришли бы к одинаковым выводам! Тем не менее данные о времени работы позволяют оценить хотя бы порядок скорости, которую следует ожидать от каждого алгоритма при сортировке записей из одного слова, так как И1Х вЂ” довольно типичный компьютер. В столбце "Память" в табл. 1 содержится некоторая информация об обьеме вспомогательной памяти, используемой каждым алгоритмом, в единицах длины записи.
Здесь буквой с обозначена доля записи, необходимая для одного поля связи; так, например, К(1 + с) означает, что методу требуется пространство для Т записей и д' полей связи. В асимптотических оценках среднего и максимального времени, приведенных в табл. 1, учитываются только главные члены, доминирующие прн больших М в предположении случайных исходных данных; с обозначает произвольную константу. Эти формулы могут иногда ввести в заблуждение, поэтому указано также фактическое время выполнения программы для двух конкретных последовательностей исходных данных. Случай Х = 16 относится к шестнадцати ключам, так часто появлявшимся в примерах раздела 5,2, а случай Х = 1000 относится к последовательности Кы Кю ..
Крова, определенной формулами К~ее~ = 0; Кп-~ = (3141592621К„+ 2113148651) шоб 10'е. Для получения характеристик каждого алгоритма, представленного в таблице, использовалась достаточно совершенная программа для И1Х, как правило, учитывающая усовершенствования, которые описаны в упражнениях. Размер байта при выполнении этих программ принят равным 100. Для внетиией сортпировкп необходимы методы, отличающиеся от методов внутренней сортировки, потому что предполагается использование сравнительно простых структур данных и Гюльшое внимание уделяется уменьшению времени ввода- вывода. В разделе 5,4.6 рассматриваются интересные методы, разработанные для сортировки данных на магнитных лентах, а в разделе 5.4.9 обсуждается использование дисков и барабанов.
Конечно, сортировка — не единственная тема этой главы. Попутно мы много узнали о том, как работать со структурами данных, обращаться с внешней памятью, анализировать алгоритмы, и о том, как изобретать... новые алгоритмы. $ О о о .и .О" о о 4» СО СО )' со О съ ч' О сч О) с сч ОС о: И И )О С« с сч со Сс О СО О В| сч й + й. ~ О) ЬС + ~ ~:Я со ь О О + с« + 3В сч ~ 4 о со +" с О О + и В О О Я ~В с со О 4) +~ ~ + со + К+ О О О + + О + О С« сч С'4 О с« ХД 4 Ю мЪ С« Я С« ис ~;й со Д Сс а о а СО Ж сс сч сч ЧС О) ) С4 С'4 Ъ Ю а с. а о О » о о а а о ,ч и ч Я о хч о х )» О а 3 о и а ОО. Д~ О О о $ и О ю и 1 О О 3 Д а о о $ а Д о о "и к х о 'и о Оо о а и о ч о Ф "Д И а и а о а х й О" х е 5 Оо «о СО Е И о Х ( а й Я Ы М о 5 Е ч са Ос Б с а В 1- Х со о а й Д «ф СО Ф о о «О м «о ж ж «о Ж а Д ущ аоод анисг1« «аиьиосэ«.
5 й 6 Е О О Оо Е ч)» о ф я сс О Х ~ Ф„" д«оо Л ~О и, о й О и о о х о Х О И р ОО ~ Бх а о О О О ИС Примечания к табл. 1 а Ключи тачько из трех цифр Ь Ключи только из шести цифр (т. е. из трех байтов) с Вывод не перекомпонован; результирующая последовательность определяется неявно ссылками или счетчиками л) Смещение выбирается, как в 5.2.1-(11); несколько лучшая последовательность появляется в упр. 5.2.1 -29 е М = 9, если использовать Бйй; для варианта с 91Ч добавить к среднему времени выполнения 1.60% Е М = 100 (размер байта) я М = 34. так как 2зл > 10ле > 2зз Ь Поскольку теория ллеполная, данные о среднем времени получены эмпирически л Оценка среднего времени базируется на предположении о равномерном распределении ключей 1 Дальнейшее совершенствование программы, о котором упоминается в тексте раздела и упражнениях, относящихся к этой программе, могут уменыпить время выполнения Ранние разработки.
Поиск прототипов современных методов сортировки возвращает нас в 19 век, когда были изобретены первые машины для сортировки. В Соединенных Штатах Америки перепись всех граждан проводилась каждые 10 лет, н уже к 1660 году проблема, связанная с обработкой огромных по объему данных переписи стала очень острой. В самом деле, число одиноких (т. е. не состоящих в браке) граждан не подсчитыввлось ежегодно, хотя вся необходимая информация собиралась. Герман Холлерит (Неппэл НойеблЬ), двадцатилетний служащий Бюро переписи, изобрел остроумный электрический табулятор, отвечающий нуждам сбора статистики, и около ста его машин успешно использовались при обработке данных переписи 1890 года. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
