а также по масти

Одна карта предшествует другой, если либо (i) она младше по масти, либо (ii) масти обеих карт одинаковы, но она младше по достоинству. (Это частный случай лексикографического упорядочения на множестве упорядоченных пар предметов; см. упр. 5-2.) Таким образом, получаем

A*<2*<--<K*<A<0><--<Q4KK<k.

Можно было бы рассортировать карты одним из обсуждавшихся ранее методов. Люди, как правило, пользуются способом, по сути, аналогичным обменной поразрядной сортировке. Естественно рассортировывать карты сначала по мастям, разложив их в четыре стопки, а затем перекладывать карты внутри каждой стопки до тех пор, пока они не будут упорядочены по достоинству.

Но существует более быстрый способ! Сначала разложим карты в 13 стопок лицевой стороной вверх по их достоинству. После этого соберем все стопки вместе: снизу - тузы, затем - двойки, тройки и т. д. и сверху - короли (лицевой стороной вверх). Далее перевернем колоду рубашками вверх и снова разложим ее, на этот раз в четыре стопки по масти. Сложив вместе полученные стопки так, чтобы внизу были трефы, затем бубны, черви и пики, получим упорядоченную колоду карт.

Та же идея годится для сортировки числовых и буквенных данных. Почему же она работает - приводит к верному результату? Потому что (в нашем примере с игральными картами), если две карты при последнем раскладе попали в разные стопки, то они имеют разные масти, так что карта с меньшей мастью младше. Если же карты одной масти, они уже находятся в нужном порядке вследствие предварительной сортировки. Иначе говоря, при втором раскладе в каждой из четырех стопок карты будут расположены в порядке возрастания. Это рассуждение можно распространить на более общий случай и показать, что таки.м способом можно рассортировать любое множество с лексикографическим упорядочением (подробности приводятся в упр. 5-2, в начале этой главы).

Только что описанный метод сортировки сразу не очевиден, и не ясно, кто же первый обнаружил, что он настолько удобен. В брошюре "The Inventory Simplified" (Изобретательство - это очень просто), опубликованной отделением Tabulating Machines Company фирмы IBM в 1923 году, на 19 страницах представлен интересный цифровой метод вычисления сумм произведений на электрической сортировальной машине этой фирмы. Пусть, например, нужно перемножить два числа, пробитых соответственно в колонках 1-10 и 23-25, и вычислить сумму таких произведений для большого числа карт. Сначала можно рассортировать карты по колонке 25 и найти при помощи табулятора величины ai, аг,..., ад, где Ok - сумма чисел из колонок 1-10 по всем картам, на которых в колонке 25 пробита цифра к. Затем можно рассортировать карты по колонке 24 и найти аналогичные суммы bi,b2, ,Ьд и по колонке 23, получив Ci, Сг,...,cg. Легко видеть, что искомая сумма произведений равна

ai + 202 + • • • 4- 9ад + lOi + 2062 + • • + 90Ьд + lOOci -f- 200с2 + • • + 900cg.

Такой перфокарточный метод табуляции естественным образом привел к идее поразрядной сортировки "сначала по младшей цифре", так что, по-видимому, она впервые

стала известна операторам этих машин. Первое опубликованное упоминание об этом методе содержится в ранней работе Л. Дж. Комри (L. J. Comrie), посвященной конструированию перфокарточного оборудования [IVansactions of the Office Machinery Users Assoc., Ltd. (1929), 25-37, особенно с. 28].

Чтобы выполнить поразрядную сортировку с помощью электронного компьютера, необходимо решить, как представлять стопки. Пусть имеется М стопок; можно было бы выделить М областей памяти и переслать каждую исходную запись в соответствующую область. Но это решение нас не удовлетворяет, потому что в каждой области должно быть достаточно места для хранения N элементов, и тогда потребуется память для (M+1)N записей. Такая чрезмерная потребность в памяти заставляла большинство программистов отказываться от применения поразрядной сортировки при программировании компьютеров до тех пор, пока X. X. Сьюворд (Н. Н. Seward) в Masters thesis, М. I. Т. Digital Computer Laboratory Report R-232 (1954), 25-28, не показал, что того же эффекта можно достичь, используя память всего для 2N записей и М счетчиков. Сделав один предварительный просмотр данных, можно просто посчитать, сколько элементов попадет в каждую область, а это позволит точно распределить память для стопок. Мы уже применяли эту идею при распределяющей сортировке (алгоритм 5.2D).

Итак, поразрядную сортировку можно выполнить следующим образом: сначала выполнить распределяющую сортировку по младшим цифрам ключей (в системе счисления с основанием М) и переместить при этом записи из области ввода во вспомогательную область; затем осуществить еще одну распределяющую сортировку по следующей цифре, переместив на сей раз записи обратно в исходную область, и так до тех пор, пока после завершающего просмотра (сортировки по старшей цифре) все ключи не окажутся расположенными в нужном порядке.

Если имеется десятичная машина, а ключи - 12-разрядные числа и если N весьма велико, то можно выбрать М = 1000 (считая три десятичные цифры за одну в системе счисления с основанием 1 ООО). Независимо от величины N сортировка будет выполнена за четыре просмотра. Аналогично, если имеется двоичная машина, а ключи - 40-разрядные двоичные числа, то можно положить, что М = 1024 = 2°, и также завершить сортировку за четыре просмотра. Фактически каждый просмотр состоит из трех групп операций (подсчет, распределение памяти, перезапись). Э. Г. Френд (Е. Н. Friend) [JACM 3 (1956), 151] предложил комбинировать два из этих трех действий, заплатив за это добавлением еще М ячеек: накапливать значения счетчиков для (А; + 1)-го просмотра одновременно с перезаписью при к-м просмотре.

В табл. 1 показано применение поразрядной сортировки к нашим 16 ключам при М = 10. При таких малых N поразрядная сортировка, как правило, не особенно эффективна, так что этот маленький пример предназначен, главным образом, для того, чтобы продемонстрировать достаточность метода, а не его эффективность.

Искушенный современный читатель заметит, однако, что идея использования счетчиков для распределения памяти привязана к старомодным понятиям о последовательном выделении памяти и соответственно о последовательном размещении данных в памяти. Нам же известно, что специально для работы с множеством таблиц переменной длины придумано связное распределение. Поэтому для поразрядной сортировки естественно будет воспользоваться связными структурами данных.

Таблица 1

ПОРАЗРЯДНАЯ СОРТИРОВКА

Область ввода: 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

Счетчики для цифр единиц: 1123121311

Распределение памяти соответственно этим счетчикам: 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

Счетчики для цифр десятков: 4210022311

Распределение памяти соответственно этим счетчикам: 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

Счетчики для цифр сотен: 2210133211

Распределение памяти соответственно этим счетчикам: 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

Поскольку каждая стопка просматривается последовательно, все, что нам нужно, - иметь при каждом элементе одну-единственную ссылку на следующий элемент. Кроме того, никогда не придется перемещать записи: достаточно откорректировать связи - и можно смело двигаться дальше по спискам. Объем необходимой памяти равен (И-б)Л + 2бЛ/ записей, где б - пространство, занимаемое одним полем связи. Довольно интересны формальные подробности этой процедуры, поскольку они дают прекрасный пример типовых операций со структурами данных, объединяющих в себе работу с последовательным и связным представлениями данных в памяти.

Алгоритм R {Поразрядная сортировка списка). Предполагается (рис. 32), что в каждой из записей Ri,...,Rn содержится поле связи LINK, ключи представляют собой последовательность из р элементов

{ai,a2,...,ap), О < < М, (1)

и отношение порядка - лексикографическое, т. е.

{ai,a2,...,ap) < {bi,b2, .. ,bp) (2)

тогда и только тогда, когда существует такой индекс j, I < j < р, что

т = bi для всех г < j, но Oj < bj. (3)

Ключи можно представлять, в частности, как числа, записанные в системе счисления с основанием М:

ахМ- + а2МР~ + Op-iM + ар. (4)

В этом случае лексикографическое отношение порядка соответствует обычному упорядочению множества неотрицательных чисел. Ключи также могут быть цепочками букв алфавита и т. д.

Во время сортировки формируются М "стопок" как в сортировальной машине для перфокарт. Стопки фактически представляют собой очереди в смысле главы 2, поскольку мы связываем их вместе таким образом, что они всегда просматриваются по принципу "первым пришел - первым вышел". Для каждой стопки имеются