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