Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 16
Текст из файла (страница 16)
Но мы замечаем, что все предложенные выше усовершенствования никоим образом не влияют на число обменов; они лишь уменьшают число избыточных повторных проверок. К сожалению, обмен двух элементов— обычно намного более дорогостояшая операция, чем сравнения ключей» поэтому все наши усовершенствования дают зна. чительно меньший эффект, чем можно было бы ожидать. Анализ показывает, что сортировка обменом и се неболь. шне улучшения хуже, чем сортировка включениями и выбором, и действительно, сортировка методом пузырька вряд ли имеет какис-то преимушества, кроме своего легко запоминающегося названия. Алгоритм шейкер-сортнровки выгодно использовать в тех случаях, когда известно, что элементы уже почти упорядочены — редкий случай на практике.
Можно показать, что среднее расстояние, на которое дол>кеи переместиться каждый из и элементов во время сорти. ровки, — зто и/3 мест. Это число дает ключ к поиску усовершенствованных, т. е. более эффективных, методов сорти- 2.2. Сортировка массивов 87 ровки, Все простые методы в принципе перемещают каждый элемент иа одну позицию иа каждом элементарном шаге.
Поэтому онн требуют порядка лв таких шагов. Любое улучшение должно основываться на принципе пересылки элементов за один цикл на большее расстояние. Далее мы обсудим три усовершенствованных метода — по одному для каждого основного метода сортировки: включения, выбора н обмена. 2.2А. Сортировка включениями с убывающим приращением Некоторое усовершенствование сортировки простыми включениями было предложено Д.
Л. Шеллом в 1959 г. Этот метод мы объясним и продемонстрируем иа нашем стандартном примере из восьми элементов (см. табл. 2.5). На первом, Таблица 2.5. Сортировиа включениями с убывающим приращением 44 55 12 6 67 4-сеотвровтат 44 18 06 42 94 55 12 67 а сортиооекот 66 18 12 42 44 65 94 67 3- оортировкат 06 12 18 42 44 55 67 94 проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В нашем примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2-сортировкой.
Наконец, на третьем проходе все элементы сортируются обычной сортировкой, или 1-сортировкой. Сначала может показаться, что необходимость нескольких проходов сортировки, в каждом из которых участвуют все элементы, больше работы потребует, чем сэкономтп, Однако д Сортировка на каждом шаге сортировки либо участвует сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок, Очевидно, что этот метод в результате дает упорядочен- ный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, по- скольку каждая 1-сортировка объединяет две группы, рас- сортированные предыдущей 21-сортировкой.
Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее оче- видно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки, Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все 1 при- ращений обозначаются через Ьо Ь,, ..., Ь, с условиями Ь~=-1, Ь„, <Ьо (2.12) Каждая И-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включения было простым, используется барьер.
Ясно, что каждая И-сортировка требует собственного барьера и что программа должна определять его место как можно проще. Поэтому массив а нужно дополнить не одной компонентой а [О], а И1 компонентами, так что теперь он описывается как ол актау[ — Ь, и] о1 Ьет Этот алгоритм представлен в виде процедуры, названной ойе11зогг [2.11] (асортировка Шелла») в программе 2.6 для 1= 4. Анализ сортировки Шелла. При анализе этого алгоритма возникают некоторые очснь сложные математические задачи, многие из которых еще ие решены. В частности, неизвестно, какая последовательность приращений дает лучшие результаты.
Однако выявлен удивительный факт, что они не должны быть кратны друг другу. Это позволяет избежать явления, которое видно в приведенном выше примере, где каждый проход сортировки объединяет две цепочки, которые ранее никак ие взаимодействовали. В действительности желательно, чтобы взаимодействие между разными цепочками аз' 2.2. Соргароеко магеиеое Ргоседиге ейейогг; сова! г = 4; таг 1,у,й,е: трех; х: !гет; пм 1 ..
г; Ь: агаву [1 .. «1 о1' тгедег; Ъеа!п Ь[!1: = 9; Ь[2[: =т 5; Ь[31:= 3; Ь[41: =- 1; йаг гп:.= 1 го г 40 Ъей1п Ь;= Ь[т[; е:=- — Ус; [место барьера! хог 1:= Ь+1 го и до Ъеа1п х:=- аЯ;,г':= — г — Ь; И е=-0 !Ъеп е:=- — Ь; е:=- а+1; а[а!:= х; ттЪ!1е х .Ьеу ( а[Я,Ьеу йо Ъей!в а[!+Л1:= аЯ',г:= / — Ь епй; а[у+Ь1:=- х епа евй епй Программа 2.6. Сортировка Шелла. происходило как можно чаще.
Можно сформулировать сле- дующую теорему: Если Ь-рассортированная последовательность [-сортируется, то она остается Ь-рассортированной. Кнут [2.8[ указывает, что разумным выбором может быть такая последовательность приращений (записанная в обрат- ном порядке): 1,4,13,40,121,..., где Ь* ~ = ЗЬа+ 1, Л~ — — ! и ! = [!одап) — 1. Он рекомендует также последовательность 1, 3, 7, 18, 31, ..., где Л» 1 = 2йа +!, Л~ = 1 и ! = [!он, п[ — 1. Дальнейший анализ показывает, что в последнем случае затраты, которые требуются для сортировки и элементов с помощью алгоритма сортировки Шелла, пропорциональны и. Хотя это — значительное улучшение по сравнению с и', мы не будем в дальнейшем обращаться к этому методу, поскольку известны алгоритмы, работающие еще лучше.
12.2.5. Сортировка с помощью дерева Метод сортировки простым выбором основан на повторном ,ыборе наименьшего ключа среди и элементов, затем среди — ! элементов и т. д. Понятно, что поиск наименьшего 2. Сортировка ключа из и элементов требует и — ! сравнений, а поиск его среди а — 1 элементов требует а — 2 сравнений.
Итак, как можно улучшить эту сортировку выборомг Это можно сде. лать только в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помошью и/2 сравнений можно определить наименьший ключ из каждой пары, при помоши Рис.
2.3. билли«есина аыбор иа лаух ключей. следуюших ау4 сравнений можно выбрать наименьший нз каждой пары таких наименьших ключей и т. д. Наконец, при помощи всего п — 1 сравнений мы можем построить дерево выбора, как показано на рис. 2.3, и определить корень как наименьший ключ (2.21. 44 12 18 44 88 12 42 84 18 П ет Рис.
2.4. Выбор наименьшего ключа. На втором шаге мы спускаемся по пути, указанному наименьшим ключом, и исключаем его, последовательно заменяя либо на «дыру» (или ключ оо), либо иа элемент, находяшийся на противоположной ветви промежуточного узла (см. рис. 2.4 и 2.5). Элемент, оказавшийся в корне дерева, вновь имеет наименьший ключ (среди оставшихся) и может быть исключен. После п таких шагов дерево становится пустым (т.
е. состоит из «дыр»), и процесс сортировки закончен. Отметим, что каждый из и шагов требует лишь 1опеп сравнений. Поэтому вся сортировка требует лишь порядка и 1опеп элементарных операций, не считая и шагов, которые необходимы для построения дерева. Это — значительное улуч- гг, сарг р шение по сравнению с простым методом, требующим н' шагов и даже по сравнению с сортировкой Шелла, которая требует пьа шагов. Конечно, при сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов„в конечном счете для хранении возросшего объема информации, получаемой на начальном проходе, нужно строить некую древовидную структуру. Наша очередная задача — найти способы эффективной организации втой информации. 1в Вт /~ /~ 94 19 Д ат Рнс гд.
Заполнение «хмр». Разумеется, было бы весьма желательно избавиться от необходимости в дырах ( — сс), которые в конце заполняют все дерево и приводят к большому количеству ненужных сравнений. Кроме того, нужно найти способ представить дерево из и элементов в п единицих памяти вместо 2а — ! единиц, как показано выше. Это действительно можно сделать с помощью метода, который его изобретатель Дж.
Уильямс (2.14] назвал пирамидальной сортировкой. Ясно, что этот метод дает существенное улучшение по сравнению с болсе привычными способами сортировки по дереву. Пирамида определяется как последовательность ключей 6» 63+и э Лг такая, что Ь~ ~~Лап (2Н 3) й,«<йм„ для всякого ( = (, ..., г/2. Если двоичное дерево представлено в виде массива, как показано на рис, 2.б, то, следовательно, деревья сортировки на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
