Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 21
Текст из файла (страница 21)
Почему же существует так много методов сортировкиу Применительно к программированию зто частный случай вопроса "Почему существует так много методов кТ", где к пробегает множество всех задач. Ответ если и неочевиден, то вполне понятен — каждый метод имеет свои преимущества и недостатки, позтому он оказывается эффективнее других при некоторых конфигурациях данных и аппаратуры.
К сожалению, неизвестен наилучший способ сортировки (если он вообще существует); имеется много наилучших методов, но только в случаях, когда известно, что сортируется, на каком компьютере и с какой целью. Говоря словами Редьярда Киплинга, "существует 9 и еще 60 способов сложить песню племени, н каждый из них в отдельности хорош". Полезно изучить характеристики каждого метода сортировки, чтобы для конкретного случая можно было сделать разумный выбор. К счастью, зта задача не столь уж громоздка, поскольку алгоритмы взаимосвязаны подчас самым причудливым способом. В начале втой главы мы ввели основную терминологию и обозначения, которые и будем использовать при изучении сортировки.
Записи должны быть рассортированы в порядке неубывания своих ключей К), Кз,..., Кт т. е., по существу, нужно найти перестановку р(1) р(2)... р(Х), такую, что Крй) < Кр)т) « " ' Кр)л) (2) В зтом разделе рассматривается ви))тренилл сортировка, когда число записей, подлежащих сортировке, достаточно мало, так что весь процесс можно провести в оперативной памяти компьютера, обладающей высоким быстродействием. В одних случаях может понадобиться физически переставлять записи в памяти так, чтобы нх ключи были упорядочены; в других можно обойтись вспомогательной таблицей некоторого вида, определяющей перестановку. Если записи н/илн ключи занимают несколько слов памяти, то часто лучше составить новую таблицу адресных ссылок, которые указывают на записи, и работать с зтими ссылками, не перемещая громоздкие записи.
Такой метод называется сортировкой таблицы адресов (рис. 6). Если ключи короткие, а сопутствующая информация в записях велика, то лля повышения скорости ключи можно вынести в таблицу адресных ссылок. Этот процесс называется сортировкой ключей. В других схемах сортировки используется вспомогательное поле связи, которое включается в каждую запись. Связи обрабатываются таким образом, что в результате все онн оказываются объединенными в линейный список, в котором каждая связь указывает на следующую по порядку запись, Этот способ называется сортировкой списка (рис, Т).
После сортировки таблицы адресов или списка можно по желанию расположить записи в порядке неубывания. Сделать это можно несколькими способами, требующими дополнительной памяти для хранения всего одной записи (см. упр. 10 и 12); или же можно просто переместить записи в новую область памяти, если она способна вместить все эти записи. Последний способ обычно вдвое быстрее первого, но требует почти в два раза больше памяти. Во многих приложениях вовсе не Ключ Записи сортировки Дополнительивл табл е сортировки Рис.
й. Сортировка таблицы ацреспых ссылок. люч Сопутствуюывя информация еле связи (после сортировки) Голова списка Рис. 7. Сортировка списка, обязательно перемешать записи, так как поля связи, как правило, вполне приемлемы для всех последующих операций обработки. Все методы сортировки, которые мы исследуем пдосконвльио", будут проилаострированы четырьмя способами: посредством а) словесного описания алгоритма, Ь) блох-схемы, с) программы дпя машины И1Х, д) примера применения етого метода сортировки к некоторому множеству из 16 чисел.
Программы для компьютера И1Х будут, как правило, написаны в предположении, что ключ — числовой и что он помещается в одном слове; иногда мы даже будем ограничивать значения ключей так, чтобы они занимали лишь часть слова. Отношением порядка с будет обычное арифметическое отношение порядка, а записи будут состоять нз одного ключа, без сопутствующей информации. Эти предположения позволяют сделать программы более короткими и простыми дпя понимания, и не составляет труда распространить их на общий случай (например, применяя сортировку таблиц адресов). Вместе с программами для ИП приводится анализ времени выполнения соответствующего алгоритма сортировки. Сортировка посредством подсчета.
Чтобы проиллюстрировать, как мы будем анализировать методы внутренней сортировки, рассмотрим идею "подсчета", упомянутую в начале данного раздела, Этот простой метод основан на том, что у-й ключ в окончательно упорядоченной последовательности превышает ровно З -1 остальных ключей. Иначе говоря, если известно, что некоторый ключ превышает ровно 27 дру- гих и если никакие два ключа не равны, то после сортировки соответствующая запись должна занять 28-е место. Таким образом, идея состоит в том, чтобы сравнить попарно все ключи н подсчитать, сколько из них меньше каждого отдельного ключа.
Очевидный способ выполнения поставленной задачи таков: ((сравнить Ку с К;) при 1 <,~' < К) при 1 <» < Ю; но нетрудно заметить, что более половины этих операций излишни, поскольку не нужно сравнивать ключ сам с собой н после сравнения К, с К» уже не надо сравнивать К» с К,. Поэтому достаточно ((сравнить Ку с К;) при 1 <» <») при 1 <» < Аг. Итак, получаем следующий алгоритм. Алгоритм С (Подсчен» сравнений). Этот алгоритм (рис. 8) сортирует записи Вы..., Вн по ключам Кы °, Кл, используя вспомогательную таблицу СООИТ[ц, ..., СООИТ[Х) для подсчета числа ключей, меньших данного. После завершения алгоритма величина СООИТ [Я + 1 определяет окончательное положение записи В . С1.
(Сбросить счетчики СООИТ,] Установить в счетчиках СООИТ [13-СООИТ[Ф] нули. С2. [Цикл по».] Выполнить шаг СЗ при» = Л, Х-1, ..., 2; затем завершить выполнение процедуры. СЗ. (Цикл по у.] Выполнить шаг С4 при 3 = » — 1, » — 2, ..., 1. С4, (Сравнить К;: К .] Если К» < К, то увеличить СООИТ[у3 на 1; в противном случае увеличить СООИТ[») на 1. $ Обратите внимание на то, что в данном алгоритме записи не перемещаются, Он аналогичен алгоритму сортировки таблицы адресов, поскольку таблица СООИТ определяет конечное положение записей; но эти методы несколько различаются, потому что СООИТ указывает, куда нужно переслать запись Вз, а не запись, которую надо переслать на место В~.
(Таким образом, таблица СОПИТ определяет перестановку, обраганпю перестановке р(1)... р(Ю): см. раздел 5.1.1.) В табл. 1 проиллюстрирован типичный ход событий при подсчете сравнений. Использован пример с 16 случайными числами, которые бьии выбраны автором еше 19 марта 1963 года.Те же самые 16 чисел будут использованы в примерах, иллюстрирующих и другие методы, анализ которых еще впереди.
В рассуждении, предшествующем этому алгоритму, мы не учитывали, что ключи могут быть равнымн. Это, вообще говоря, серьезное упущение, которое может повлечь за собой самые опасные последствия, потому что если бы равным ключам соответстновали равные счетчики, то заключительное перемещение записей было бы довольно сложным. К счастью, как показано в упр. 2, алгоритм С дает верный результат независимо от числа ровных ключей, Программа С (Подсчен» срааненнй).
Ниже приведена программа для И11, реализующая алгоритм С в предположении, что В- хранятся по адресу 1ИРОТ+ у, а СООИТ[у) — по адресу СООИТ+ у, где 1 < у < Л; состояние регистров следующее: гЦ ьз»', г12 = у, гА ги Л; = Вн гХ гв СООИТ [»3. 01 ЗТАЗТ ЕИТ1 И 1 С1. Очистка СОВИТ. ОЗ ЗТЗ СООИТ, 1 Х СОПИТВ1»- О.
Таблица 1 СОРТИРОВКА ПОСРЕДСТВОМ ПОДСЧЕТА (АЛГОРИТМ С) 677 765 703 о о о О 1 12 0 13 12 11 13 12 и 1з тз 11 13 12 11 13 12 154 509 612 о о о о о о о о о о о о О О 9 О 7 9 2 7 9 653 42 6 о о о о о о о о 1 0 2 0 з КЛЯЧИ: ( ): СООИТ (1 = Х): СООИТ (1" = 1Ч-1): СООИТ (1 = Ж вЂ” 2): СООИТ (1 = 87-3): ОООИТ (1 = А' — 4).' СОШП' (1 = 1'х' — 5): 503 087 о о о о о о о о о о о о о 512 061 908 о о о о о о о о о з 0 О 4 О 5 2 О б 170 897 275 о о о О 1 О О 2 0 о з о О 4 О О 5 О 1 6 1 СООИТ (1=2): б 1 8 О 15 3 14 4 10 5 2 7 9 11 13 12 Рис, 8.
Алгоритм 65 подсчет сравнений. )Ч > 1 > О. Сз. Бикл ло Е Переход, если К; > Кт, сооит(11 +1 -+ сооит(Я. сооитП) <- сооитВВ + 1. и. а вд. 1ч >1>1 >О. ! Время работы етой программы равно 13К+ ОА+ 5 — 4 мап1инных циклов, где Х -- число записей, А — число способов выбрать 2 предмета из )У, т, е.
(е) = л (1х'т — 01)1'2, а  — число пар индексов, таких, что 1 < 4 и Кз > К;. Значит, В число ииеерсиО перестановки К1 ... К~д," эта величина подробно анализировалась в разделе 5.1.1 (Формулы 5.1.1-(12) и 5.1.1-(13)), в котором было найдено, что для неравных ключей, расположенных в случайном порядке, В = (ппп О, аве (Ка — Х)/4, пах (Ют — )Р)/2, дев К(К вЂ” 1)(К+ 2.5)/6). 88 04 05 08 07 2Н 08 ОУ ЗН 10 11 18 18 Ц 18 4Н 18 ЬН 17 18 1У 80 1Н 81 ОЕС1 1 31Р в-2 ЕМТ1 М 1НР 1Р ЫЛ 1МРОТ, 1 1.0Х СООМТ, 1 СИРА 1МРОТ,2 ЗОЕ 4Р 103 СООИТ,2 1ИСЗ 1 ВТЗ СООМТ,2 1НР. ЬР 1МСХ 1 ОЕС2 1 12Р ЗВ НТХ СООМТ,1 ОЕС1 1 ЕИТ2 -1,1 ЗЕР 28 07 Х 1 1 1Ч вЂ” 1 1'х — 1 А А В В В В А — В А А Ж вЂ” 1- А' — 1 1Ч 1Ч Следовательно, выполнение программы С занимает от ЗЛг~ + 10Л вЂ” 4 до 5.бает + 7.5Лг — 4 машинных циклов, а среднее время работы находится посередине между этими крайними значениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
