AOP_Tom3 (1021738), страница 64
Текст из файла (страница 64)
5.2.1 — 38). Мак-Ларен вычислил среднее число обращений к памяти, приходящихся на один обрабатываемый элемент, и оказалось, что оптимальный выбор значений М и р (в предположении, что 3Х— степень двойки, ключи равномерно распределены и ВЧМг ( 0.1, так что отклонения от равномерного распределения приемлемы) описывается следующей таблицей. ние от 25 до 75% всех записей [см.
1пб Ргос. 1,е))егя 7 (1978), 1 — б; 8 (1979), 170 — 172]. В результате среднее время сортировки равномерно распределенных ключей оказалось порядка 0(зУ), но для наихудшего случая время будет составлять порядка 0(А?)об?У). Указанная статья побудила других исследователей разработать новые алгоритмы вычисления адресов, из которых наиболее удачной оказалась следующая двухуровневая схема, предложенная Маркку Тамминеном (Маг)я)гц Тапипшеп) [Х А)8ог)йшя 6 (1985), 138 — 144].
Предположим, что все ключи являются дробями из интервала ]0..1). Сначала распределим Аг записей по [А??'8] хранилищам и поставим в соответствие ключу К хранилище [К)У/8]. Далее предположим, что в хранилище к оказалось Хя записей. Если Хь < 16, можно использовать сортировку методом прямых вставок, в противном случае — сортировать так же, как предлагал Ыак-Лареи, но для М~ хранилищ (стопок), где ЛХз ш 10Хю Таммннен доказал следующую весьма существенную теорему. Теорема Т. Существует константа Т, такая, что оннсанный выше метод сортировки требует в среднем не более ТзУ операций, если только ключи являются нсзавнснмызш случайнымн числами с ограниченной и внтсгрпруемой по Рнману плотностью распределения 7'(х) прп 0 < х < 1.
(Константа Т не зависит от вида функции 7.) Дакаэатпельстива. (См. упр. 18.) Интуитивно ясно, что в результате выполнения первой фазы распределения между Ж/8 стопками будет найден интервал, на котором функция у является почти постоянной; на второй фазе ожидаемый размер стопки станет почти постоянным. $ Некоторые версии поразрядной сортировки были доведены до совершенства при работе г большими массивами буквенных строк, что описано в весьма содержательной статье Р. М. Мс1)гоу, К. Воя1и, М. П. Мс1!гоу, СошриПпб буя)ещя 6 (1993), 5-27, УПРАЖНЕНИЯ 1. [20) Алгоритм из упр. 5.2 13 наказывает, как можно выполнить распределяюшую сортировку, имея объем памяти, достаточный для хранения всего Х записей (и М полей счетчиков), я не 2?Ч записей.
Приводит ли зта идея к усовершенствованию алгоритма поразрядной сортировки, праиллюстрираваниага в табл 1? 2. [12] 51вляется ли алгоритм Н алгоритмом устойчивой сортировки? 3. [15) Объясните, пачему в алгоритме П выхалит так, чта ВОТИ[01 указывает нв первую запись в "абъединеииай" очереди даже в случае, если стопка 0 оказываемся пусшоб. ° 4. [20) Ба время выполнения алгоритма Н все М станок хранятся в виде связных очередей ('первым вошел — первым вышел"). Исследуйте идею связывания элементов стопок, как в стеке. (На рис.
33 стрелки будут указывать ие вверх, а вниз и таблица ВОТП станет не нужна.) Покажите, чта если сцеплять стоики в саатветствующем порядке, та может получиться работоспособный метод сортировки. Будет ли зтат алгоритм более простым или более быстрым'! б. [20) Какие изменения необходима внести в программу Н, чтобы аиа выполняла сартираяку не трехбайтавых ключей, в васьмибайтавых? Считается, чта старшие байты ключа К, хранятся па адресу КЕТ + 1(1;5), а три младших байта, как и раньше, — по адресу 1КРОТ+ 1(1: 3).
Какова время выполнения программы с зтими изменениями? б. [М24) Пусть дмк(з) = 2',рмкгг, гда рлгкь — вероятность того, чта после случайного просмотра поразрядной сортировки, разложившего ?у злементав на М стопок, получилось ровно к пустых стопок. а) Покажите, что дмоя ьм(з) = дмя(з) + ((1 — з)/И)дмя(в).
Ь) Найдите при помощи указанного соотношения простые выражения для математического ожилвння и дисперсии этого распределения вероятностей как функций от ЛХ и Гг. 7. [20) Проанализируйте, в чем состоит сходство н отличие алгоритма К и облгенной поразрядной сортировки (алгоритм о.2.2К). 8. [20) В алгоритмах поразрядной сортировки, обсуждавшихся в тексте раздела, предполагалось, что все сортируемые ключи неотрицательны. Какие изменения следует внести в зти алгоритмы в том случае, когда ключами являются и отрицательные числа, представленные в даполнишельном или одран|нам коде? 9.
[20) (Продолжение упр. 8.) Какие изменения нужно внести в этн алгоритмы в случае, когда ключами являются числа, представленные в виде абсолютной величины со знаком? 10. [20) Разработайте алгоритм поразрядной СЦ-сортировки, использующий связное распределение памяти. (Так как размер подмассивов все уменьшается, разумно уменьшить М, а для сортировки коротких массивов применить метод, отличный от поразрядной сортировки.) 11. [10[ Перестановка 1б исходных чисел, показанная в табл.
1, содержит вначале 41 инверсию. По завершении сортировки инверсий, разумеется, нет совсем. Сколько инверсий осталось бы в массиве, если пропустить первый просмотр и выполнить поразрядную сортировку лишь по цифрам десятков н сотен' Сколько инверсий останется, если пропустить как первый, так и второй п?зосмотрыт 12. [24[ (М. Д. Мак-Ларси (М. П, МасЬагеп).) Предположим, алгоритм К применили только к р старшим цифрам реальных ключей; тогда массив, если его читать по порядку, указанному связямн, почти рассортнрован. но ключи, старшие р цифр которых совпадают, могут быть неупорядочены, Придумайте такой алгоритм перекомпановки записей в пределах того же объема памяти, чтобы ключи расположились в порядке К1 < Кз « .. Кл. [Указание.
Частный случай, когда массив полностью рассортирован, можно найти в ответе к упр. 5.2-12, его можно скомбинировать с простыми вставками без потери эффективности, так как в массиве осталось мало инверсий.) 13. [40) Реализуйте метод внутренней сортировки, предложенный в тексте в конце этого раздела, и разработайте программу сортировки случайных данных за 0(М) машинных циклов, требующую всего 0(~/оц) дополнительных ячеек памяти. 14. [22[ Пооледовательпость игральных карт можно рассортировать в порядке возрастания от верхней карты к нижней за два просмотра, раскладывая их каждый раз лишь в две стопки: Разложите карты лицевой стороной вниз в две стопки, содержащие А 2 ...
1 Ц К соотяетственно (от нижней карты к верхней). Затем положите вторую стопку пояерх первой, поверните колоду лицевой стороной вверх и разложите в две стопки: А 2 9 3 10 и 4 у Ь б и К 7 б. Сложите эти две стопки и поверните их лицевой стороной вверх. Колода будет рассортирована. Докажите, что приведенную выше последовательность карт нельзя рассортировать в порядке убывания К Я 1 ...
2 А от верхней карты к нижней за два просмотра, даже если разрешено раскладывать карты в три стопки (Сдавать карты нужно всегда сверху катоды, поворачивая их рубашкой вверх. На рисунке верхняя карта колоды изображена справа, а нижняя — слева.) 1б. (Азйб) Рассмотрите задачу из упр. 14 для случая, когда карты раздаются лицевой стороной вверх, а не вниз. Таким образом, один просмотр можно потратить на преобразование возрастающего порядка в убывающий, Сколько нужно просмотров? ь 16. Р251 Разработайте алгоритм сортировки строк оы ..., аю состоящих нз тп букв в лексикографическам порядке.
Суммарное время выполнения этого. алгоритма должно быть порядка О(т+ п + )Ч), где )Ч = )о~) т + )о„) — суммарная длина всех строк. 17. (1б) Почему в двухуровневом методе сортировки, предложенном Таммииеном (скс теорему Т), метод, аналогичный алгоритму К)ак-Ларена, используется на втором и не используется на первом уровне? 18. (НМйб) Докажите теорему Т.
Указание. Сначала покажите, что алгоритм Мак-Ларена действительно выполняет в среднем О(В)Ч) операций, если его применять по отношению к независимым случайным ключам, для которых функция плотности вероятностей удовлетворяет ущювию,у(х) < В при О < х < 1. Для сортировки корней и слов нвм понадобится 11ОО ящиков и лотков для Фоом.
— Д>КОРД>К В. ВИГРАМ (6ЕОЙ6Е М ЧЧ!6ПАМ) (1943) 5.4. ВНЕШНЯЯ СОРТИРОВКА Пгишло вгкмя заняться интересными задачами, возникающими в том случае, когда записей болыпе, чем может поместиться в быстродействующую оперативную память. Внешняя сортировка в корне отличается от внутренней 1хотя в обоих случаях необходимо расположить записи данного файла в порядке неубывания), и объясняется это тем, что время доступа к массиву на внешних носителях жестко ограничено. Структура данных должна быть такой, чтобы сравнительно медленные периферийные запоминающие устройства (на магнитных лентах, дисках., барабанах и т. д.) могли удовлетворить потребности алгоритма сортировки. Поэтому большинство изученных до сих пор методов внутренней сортировки (вставка, обмен, выбор) фактически бесполезно для внешней сортировки; необходимо рассмотреть всю проблему заново.
Предположим, например, что предназначенный для сортировки файл состоит из 5 000 записей В~ Ла... Взаааааа длиной по 20 слав (хотя ключи 11, не обязательно должны иметь такую длину). Как быть, если во внутренней памяти данной машины помещается одновремешю только 1000 из этих записей? Сразу напрашивается такое решение: рассортировать каждый из пяти подфайлов гг1 - гг1аааааа, тт|ааааа1 . гсзаааааа,, В4ааааа1 гсааааааа по отдельности и затем слить полученные подфайлы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
