Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 48
Текст из файла (страница 48)
Данный метод является усовершенствованным вариантом метода вставок в несколько списков (программа 5.2.1М), который, по существу, представляет собой случай р = 1. В упр. 12 приводится интересная процедура Мак-Ларена для окончательной перекомпановки записей после частичной сортировки массива с помощью списков. Если воспользоваться методами нз алгоритма 5.2П и упр, 5.2-13. то можно обойтись без полей связи; при этом в дополнение к памяти, занятой самими записями, потребуется всего 0(~/Х) ячеек. Если исходные данные распределены равномерно, то среднее время сортировки пропорционально Х.
В. Добосевич (%. ПоЪоэ1еи!сг) получил хорошнй результат при использовании СЦ-сортировки в отношении массивов значительной длины. Процесс распределения был построен таким образом, что для первых М/2 стопок гарантировалось получе- можно независимо рассортировать по другим мешкам, соответствующим все более мелким районам. (Разумеется, прежде чем продолжить сортировку писем, их можно переправить поближе к месту назначения.) Принцип "разделяй и властвуй" весьма привлекателен, и единственная причина его непригодности для сортировки перфокарт состоит в том, что большое количество стопок приводит к путанице.
Этим же явлением объясняется относительная эффективность алгоритма К (хотя здесь предпочтение отдается анализу, начатому с младших разрядов), потому что никогда не приходится работать более чем с М стопками и стопки приходится сцеплять всего р раз. С другой стороны, нетрудно построить СЦ-поразрядный метод с помощью связного распределения памяти с отрицательными связямн для обозначения границ между стопками, как в алгоритме 5.2.4Ъ (см. упр.
10). Пожалуй, наилучший компромиссный выход указал М. Д. Мак-Дарен (М. О. Мас1.агеп) (.1АСЛ4 13 (1966), 404-41Ц, который предложил использовать МЦ-сортировку, как в алгоритме В„но в применении к старшим рирлдвм. Это не будет полной сортировкой массива, но в результате массив станет почти упорядоченным. т. е. в нем останется очень мало инверсий, так что для завершения сортировки можно будет воспользоваться методом простых вставок.
Наш анализ программы 5.2.1М применим и к этой ситуации; если ключи распределены равномерно, то после сортировки массива по старшим р цифрам в нем останется в среднем 4 Х(Х вЂ” 1)ЛХ инверсий (см. формулу 5.2.1 — (17) и упр. 5.2.1 — 38). Мак-Чареи вычислил среднее число обращений к памяти, приходящихся на один обрабатываемый элемент, и оказалось, что оптимальный выбор значений ЛЛ н р (в предположении, что М— степень двойки, ключи равномерно распределены и Х/ЛР < 0.1, так что отклонения от равномерного распределения приемлемы) описывается следующей таблицей. иие от 25 до 75% всех записей [см.
1пб Ргос, 5сгсегв 7 (1978), 1-6; 8 (1979), 170-172[, В результате сргдиее время сортировки равномерно распределенных ключей оказалось порядка 0(Х), ио для наихудшего случая время будет составлять порядка 0(Ю!оба). Указанная статья побудила других исследователей разработать новые алгоритмы вычисления адресов, из которых наиболее удачной оказалась следующая двухуровневая схема, предложенная Маркку Таммииеиом (Маг1йп Ташпппеп) [Х А!8огййшв 6 (1985), 138-144[.
Предположим, что все ключи являются дробями из интервала [0..1). Сначала распределим Х записей по [)У/8) хранилищам и поставим в соответствие ключу К хранилище [Кйу/8). Далее предположим, что и хранилище к оказалось № записей. Если № < 16, можно использовать сортировку методом прямых вставок, в противном случае ' — сортировать так же, как предлагал Мак-Ларси, ио для Мт хранилищ (стопок), где Мз ш 10№. Таммииеи доказал следующую весьма существенную теорему. Теорема Т. Существует константа Т, такая, что описанный выше метод соргнровкн требует в среднем не более Т?У операщгй, если только ключи являются незавнснмымп слушайнымп чнсламп с ограниченной я интегрируемой по Рпману плотностью распределенз?я /(т) прн 0 < я < 1.
(Константа Т не зависит от вида функции /.) Доаиатеяьсшео. (См. упр. 18.) Интуитивно ясно, что в результате выполнения первой фазы распределения между У/8 стопками будет найден интервал, иа котором функция / является почти постоянной; иа второй фазе ожидаемый размер стопки станет почти постоянным. $ Некоторые версии поразрядной сортировки были доведены до совершенства при работе с большими массивами буквеииых строк, что описано в весьма содержательной статье Р.
М. Мсйгоу, К. Вовс!с, М. П. Мсйгоу, Сотрибпй бувСшпв 6 (1993), 5-27. УПРАЖНЕНИЯ 1, [вд[ Алгоритм из упр. 5.2 .13 показывает, квк можно выполнить рвспределяюшую сортировку, имея абьем памяти, достаточный для храиевия всего?Ч записей (и М палей счетчиков), а ие 2Х записей. Приводит ли этв идея к усовершенствованию алгоритма поразрядной сортировки, проиллюстрироваииого в табл.
1? 2. [13[ Является ли алгоритм К алгоритмом устойчивой сортировки? 3. [Ы[ Объясните, почему в алгоритме Н выходит так, что ВОТМ 101 указывает иа первую запись в 'объединенной" очереди даже в случае, если степка О оказывается пчсшао. 4. [ВУ[ Во время выполнения алгоритма К все М стопок хранятся в виде связных очередей ("первым вошел — первым вышел"). Исследуйте идею связывания элементов стопок, как в стеке. (На рис. 33 стрелки будут указывать ие вверх, а вниз и таблица ВОТй станет не нужна.) Покажите, что если сцеплять стопки в соответствующем порядке, то может получаться работоспособный метод сортировки. Будет ли этот алгоритм более простым или бале быстрым? Ь. [20[ Какие изменения необходимо внести в программу К, чтобы оив выполняла сортировку ие трехбвйтовых ключей, а восьмибайтовых? Считается, что старшие байты ключа К, хранятся по адресу ХВТ + 1(1: 3), в три младших байта, как и раньше, — по эдресу Тйрв?+ 1(1: 3).
Каково время выполнения программы с этими измеиеииями? 6. [М24[ Пусть емк(э) = 2;рмюэя~., где рмль -- вероятность того, что после случайного просмотра порвзрядиай сортировки, разложившего ?Ч элементов иа М стопок, получилось ровно к пустых стопок. а) Покажите, что дьцм+П(з) = дмк(з) + ((1 — з)/М)ймя(е). Ь) Найдите при помощи указанного соотношения простые выражения для математического ожидания и дисперсии этого распределения вероятностей как функций от М и Х. 7. [20] Прошгализируйте, в чем состоит сходство и отличие алгоритма В и обменной поразрядной сортировки (алгоритм 5.2.2В).
6. [20] В алгоритмах поразрядной сортировки, обсуждавшихся в тексте раздела. предполагалось, что все сортируемые ключи иеотрипательша. Какие изменения следует внести в эти алгоритмы в том скучав, когда ключами являются н отрицательные числа, представленные в дояолкигпелькем или обратлкоы коде? 9. [20] (Продолжение упр, 3.) Какие изменения нужно внести в эги алгоритмы в случае, когда ключами являются числа, представленные а виде абсолютной величиям со эконому 10.
',30] Разработайте алгоритм поразрядной СЦ-сортировки, использующий связное распределение памяти. (Так как размер подмассивов все уменыпается, разумно уменьшип М, а для сортировки коротких массивов применить метод, отличный от поразрядной сортировки.) 11.
[16] Перестановка 16 исходнмх чисел, показанная в табл. 1, содержит вначале 41 инверсию. По завершении сортировки инверсий, разумеется, нет совсем. Сколько инверсий осталось бы в массиве, если пропустить первый просмотр и выполнить поразрядную сортировку лишь по цифрам десятков и сотен? Сколько инверсий останется, если пропустить как первый, так и второй просмотрыу 12. [2(] (М, Д. Мак-Ларек (М. О, Мас1.шеп).) Предположим, алгоритм К применили только к р старшим цифрам реальных ключей; тогда массив, если его читать по порядку, указанному связями. почти рассортирован.
но ключи, старшие р цифр которых совпадают, могут быть неупорядочены. Придумайте такой алгоритм перекомпоновкн записей в пределах того же объема памяти, чтобы ключи расположились в порядке К~ < Кэ < < Кя. [Указание. Частный скучай, когда массив пошюстью рассортнроваи, можно найти в ответе к упр. 5.2-12, его можно скомбинировать с простыми вставками без потери эффективности, так как в массиве осталось мало инверсий,] 13.
[Х0] Реализуйте метод внутренней сортировки, предложенный в тексте в конце этого раздела, и разработайте программу сортировки случайных данных за 0(Х) машинных циклов, требующую всего 0(/М ) дополнительных ячеек памяти. 14. [22] Последовательность игральных карт можно рассортировать в порядке возрастания от верхней карты к нижней за два просмотра, раскладывая их каждый раз лишь в две стопки: Разложите карты лицевой стороной вниз в две стопки, содержащие А 2 ... 1 Ц К соответственно (от нижней карты к верхней). Затем положите вторую стопку поверх первой, поверните колоду лицевой стороной вверх н разложите в две стопки: А 2 9 3 10 и 4 1 Ь б Ц К 7 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
