Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 46
Текст из файла (страница 46)
(В упр. 5.2.2-30 рассматривается анаэогичная проблема применительно к быстрой сортировке.) 23. [МЯО) В уцр. 13 и 14 анализируется "восходящая", или итеративная, версия сорти- ровки методом слияния, где параметр цены с(М) сортировки А! элементов удовлетворяет рекуррентному соотношению с(!7) = с(2 )+с(!э'-2 )+/(2",Х вЂ” 2~) при 2' < Ж < 2ьы и /(т, и) есть цена слияния т элементов с и.
Проанализируйте "нисходящую" версию или рекурреитное соотношение наподобие "разделяй и властвуй", с(Х) = с([Ю/2)) +с([!7/2))+/([А!/2), $!7/2)) при !7 > 1, которое имеет место при использовании рекуррентной программы сортировки. $.2.5. Сортировка методом распределения Рассмотрим теперь интересный класс методов сортировки, который, как показано в разделе 8.4.7, по своей сути является обрагпнэьм слиянию. Читателям, знакомым с перфокарточным оборудованием, хорошо известна эффективная процедура, применяемая в машинах для сортировки карт задолго до появления электронных компьютеров.
Ту же идею можно использовать к для программирования компьютеров. Она общеизвестна под названиями "поразрядная сортировка", "карманная сортировка" (Ъпскес эогс!пй) и "цифровая сортировка" (с)!К)1а! зогз!пй), поскольку базируется иа анализе цифр ключей. Предположим, необходимо рассортировать колоду из 52 игральных карт. Определим упорядочение по старшинству (достоинству) карт в масти й < 2 < 3 < 4 < б < б < 7 < 8 < 9 < 10 < Л < Ц < К, а также по масти в<0< 2<а. Одна карта предшествует другой, если либо (1) она младше по масти, либо (й) масти обеих карт одинаковы, но она младше по достоинству.
(Это частный случай лекспкографического упорядочения на множестве упорядоченных пар предметов; см. упр. 5-2.) Таким образом, получаем йй1<24«" Кйб<60«" Оф<КФ. Можно было бы рассортировать карты одним из обсуждавшихся ранее методов. Люди, как правило, пользуются способом, по сути, аналогичным обменной поразрядной сортировке.
Естественно рассортировывать карты сначала по мастям, разложив их в четыре стопки, а затем перекладывать карты внутри каждой стопки до тех пор, пока они не будут упорядочены по достоинству. Но существует более быстрый способ! Сначала разложим карты в 13 стопок лицевой стороной вверх по их достоинству. После этого соберем все стопки вместе: снизу — тузы, затем — двойки, тройки и т. д. и сверху — короли (лицевой стороной вверх). Далее перевернем колоду рубашкамн вверх и снова разложим ее, на этот рвз в четыре стопки по масти.
Сложив вместе полученные стопки так, чтобы внизу были трефы, затем бубны, черви и пики, получим упорядоченную колоду карт. Та же идея годится для сортировки числовых и буквенных данных. Почему же она работает — приводит к верному результату? Потому что (в нашем примере с игральными картами), если две карты при последнем раскладе попали в разные стопки, то они имеют разные масти, так что карта с меньшей мастью младше.
Если же карты одной масти, онн уже находятся в нужном порядке вследствие предварительной сортировки. Иначе говоря, при втором раскладе в каждой нз четырех стопок карты будут расположены в порядке возрастания. Это рассуждение можно распространить на более общий случай и показать, что таким способом можно рассортировать любое множество с лексикографнческим упорядочением (подробности приводятся в упр. 5-2, в начале этой главы). Только что описанный метод сортировки сразу не очевиден, и не ясно, кто же первый обнаружил, что он настолько удобен.
В броппоре "ТЬе 1птепгогу Яппр(1йед" (Изобретательство — это очень просто), опубликованной отделением ТаЬп1аг1пя МасЬ1пез Сошрапу фирмы 1ВМ в 1923 году, на 19 страницах представлен интересный цифровой метод вычисления сумм произведений на электрической сортировальной машине этой фирмы. Пусть, например, нужно перемножить два числа, пробитых соответственно в колонках 1-10 и 23-25, и вычислить сумму таких произведений лля большого числа карт.
Сначала можно рассортировать карты по колонке 25 н найти при помощи табулятора величины ам аю ..,, аэ, где аэ — сумма чисел нз колонок 1-10 по всем картам, на которых в колонке 25 пробита цифра 6. Затем можно рассортировать карты по колонке 24 и найти аналогичные суммы 6м 6э....,6э и по колонке 23, получив сы сз,...,сэ. Легко видеть, что искомая сумма произведений равна а~+2аз+ +9аэ+ 106|+206э+ ° +906э+100с~+200сэ+ +900сэ Такой перфокарточный метод табуляции естественным образом привел к идее поразрядной сортировки "сначала по младшей цифре", так что, по-виднмому, она впервые стала известна операторам этих машин.
Первое опубликованное упоминание об этом методе содержится в ранней работе Л. Дж. Комри (1.. Я. Соп1Не), посвященной конструированию перфокарточного оборудования (2гапзасгуопз оу Йе 01йсе МасЬ1пегу Узегз' Аэзос, ЕИ. (1929), 25-37, особенно с. 28). Чтобы выполнить поразрядную сортировку с помощью электронного компьютера, необходимо решить, как представлять стопки. Пусть имеется М стопок; можно было бы выделить М областей памяти и переслать каждую исходную запись в соответствующую область, Но это решение нас не удовлетворяет, потому что в каждой области должно быть достаточно места для хранения Ю элементов, и тогда потребуется память для (М+ 1)Ю записей.
Такая чрезмерная потребность в памяти заставляла большинство программистов отказываться от применения поразрядной сортировки при программировании компьютеров до тех пор. пока Х. Х. Сьюворд (Н. Н. Бежать) в Л4азгег'з гпезЬ, М. 1. Т. Р1811а1 Согпрп1ег 1аоогагогу Верогг Н-232 (1954), 25-28, не показал, что того же эффекта можно достичь, используя память всего для 2Ж записей и Лй счетчиков.
Сделав один предварительный просмотр данных, можно просто посчитать, сколько элементов попадет в каждую область, а это позволит точно распределить память для стопок. ГИы уже применяли эту идею при распределяющей сортировке (алгоритм 5.2Р). Итак, поразрядную сортировку можно выполнить следующим образом: сначала выполнить распределяющую сортировку по младшим цифрам ключей (в системе счисления с основанием М) и переместить при этом записи из области ввода во вспомогательную область; затем осуществить еще одну распределяющую сортировку по следующей цифре, переместив на сей рэз записи обратно в исходную область, и так до тех пор, пока после завершающего просмотра (сортировки по старшей цифре) все ключи не окажутся расположенными в нужном порядке.
Если имеется десятичная машина, а ключи — 12-разрядные числа и если Х весьма велико, то можно выбрать М = 1000 (счнтая три десятичные цифры за одну в системе счисления с основанием 1 000). Независимо от величины Ю сортировка будет выполнена за четыре просмотра. Аналогично, если имеется двоичная машина, а ключи — 40-разрядные двоичные числа, то можно положить, что ЛУ = 1024 = 2'е, и также завершить сортировку за четыре просмотра. Фактически каждый просмотр состоят из трех групп операций (подсчет, распределение памяти, перезапись). Э. Г. Френд (Е.
Н. гг1епб) «3АСЛ1 3 (1956), 151] предложил комбинировать два из этих трех действий, заплатив за это добавлением еще М ячеек: накапливать значения счетчиков для (й + 1)-го просмотра одновременно с перезаписью при й-м просмотре. В табл. 1 показано применение поразрядной сортировки к вашим 16 ключам при М = 10. При таких малых Х поразрядная сортировка, как правило, не особенно эффективна, так что этот маленький пример предназначен, главным образом, для того, чтобы продемонстрировать достаточность метода, а не его эффективность, Искушенный современный читатель заметит, однако, что идея использования счетчиков для распределения памяти привязана к старомодным понятиям о последовательном выделении памяти и соответственно о последовательном размещении данных в памяти. Нам же известно„что специально для работы с множеством таблиц переменной длины придумано связное распределение. Поэтому для поразрядной сортировки естественно будет воспользоваться связными структурами данных.
Таблица 1 ПОРАЗРЯДНАЯ СОРТИРОВКА 503 087 5!2 061 908 !70 897 275 653 426 154 509 612 6Т7 765 703 Область ввода: Счетчики для цифр единиц: 1 1 2 3 1 2 1 3 ! 1 Распределение памяти соответственно этим счетчикам: 1 2 4 7 8 10 11 14 15 16 Вспомогательная область: 170 061 512 б!2 503 653 703 154 275 765 426 087 897 бТ7 908 509 Счетчики для цифр десятков: 4 2 1 0 0 2 2 3 1 1 этим счетчикам: 4 б Т 7 7 9 11 14 15 16 703 906 509 512 612 426 653 154 061 765 170 275 677 087 897 Распределение памятп соответственно Область вводы 503 Счетчики для цифр сотен: 2 2 1 0 1 3 3 2 1 1 Распределение памяти соответственно этим счетчикам: 2 4 5 о б 9 12 14 15 16 Вспомогательная область: 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 Поскольку каждая стопка просматривается последовательно, все, что нам нужно,— иметь при каждом элементе одну-единствеиную ссылку на следующий элемент.
Кроме того, никогда не придется перемещать записи: достаточно откорректировать связи — и можно смело двигаться дальше по спискам. Объем необходимой памяти равен (1+ с) ЛХ+ 2сМ записей, где е — пространство, занимаемое одним полем связи. Довольно интересны формальные подробности этой процедуры, поскольку оин дают прекрасный пример типовых операций со структурами данных, объединяющих в себе работу с последовательным и связным представлениями данных в памяти. Алгоритм К (Поразрядная соршмровка списка), Предполагается (рис. 22), что в каждой из записей В1,...
„Нгг СОДЕРжится поле связи 1.1МК, ключи представляют собой последовательность из р элементов (аг аз, ° ° ар) 0 < аг < ЛХ и отношение порядка — лексикографическое, т, е. (а,а .....,а„) < (Ь,,Ь,...,Ь ) тогда и только тогда, когда существует такой индекс Х, 1 < Х < р, что а,=Ь1 длявсехэ<уг но а <Ь.
Ключи можно представлять, в частиостиг как числа, записанные в системе счисле- ния с основанием М: 01ЛХ' '+ атМв . ° ° + а„!ЛХ+ ар. В этом случае лекснкографическое отношение порядка соответствует обычному упорядочению множества неотрицательных чисел. Ключи также могут быть цепочками бука алфавита и т. д. Во время сортировки формируются М "стопок", как в сортировальной машине для перфокарт. Стопки фактически представляют собой очереди в смысле главы 2, поскольку мы связываем их вместе таким образом, что они всегда просматриваются по принципу 'первым пришел — первым вышел': Для каждой стопки имеются Рнс, 32.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
