ВУЗ:
Составители:
89
Но существует более быстрый способ. Он заключается в том, что
сначала карты следует разложить в 13 стопок лицевой стороной вверх по
их достоинству. Затем собрать все стопки вместе: снизу тузы, затем двой-
ки, тройки и т.д. и сверху короли (лицевой стороной вверх). Перевернуть
колоду рубашками вверх и снова разложить, на этот раз в четыре стопки по
масти. Сложив вместе полученные стопки так, чтобы внизу были трефы,
затем бубны, черви и пики, получим упорядоченную колоду карт.
Идея такой сортировки является правильной, потому что, если две
карты при последнем раскладе попали в разные стопки, то они имеют
разные масти, так что карта с меньшей мастью младше другой карты.
Если же две карты имеют одну и ту же масть, то они уже находятся в
нужном порядке благодаря предварительной сортировке. Заметим, что
это доказательство можно обобщить на сортировку любого множества в
лексикографическом порядке.
Такой метод упорядочения естественным образом приводит к идее
поразрядной сортировки. Чтобы выполнить поразрядную сортировку с
помощью ЭВМ, необходимо определиться со способом представления
стопок. Если имеется М стопок, то можно выделить М областей памяти и
пересылать каждую исходную запись в соответствующую область. Но
при этом в каждой области должно быть достаточно места для хранения
N элементов, и тогда потребуется пространство под (М+1)N записей. Од-
нако того же эффекта можно добиться, имея в распоряжении пространст-
во всего под 2N записей и М счётчиков. Сделав один предварительный
просмотр данных, можно установить, сколько элементов попадает в каж-
дую область, что даст возможность точно распределить память под стоп-
ки. Такая идея уже была применена при сортировке распределяющим
подсчётом (алгоритм D).
Следовательно, поразрядную сортировку можно выполнить так.
Сначала произвести распределяющую сортировку по младшим цифрам
ключей (в системе счисления с основанием М), переместив записи из об-
ласти ввода во вспомогательную область. Затем выполнить ещё одну
распределяющую сортировку, но уже по следующей цифре, переместив
записи обратно в исходную область. Продолжать подобные действия до
тех пор, пока после завершающей сортировки по старшей цифре все
ключи не окажутся расположенными в нужном порядке.
В таблице показано применение поразрядной сортировки к нашим
16 ключам при М = 10. При таких малых N поразрядная сортировка, как
правило, неэффективна, так что этот пример предназначен главным образом
для того, чтобы продемонстрировать достаточность применяемого метода:
Область
ввода
503
087
512
061
908
170
897
275
653
426
154
509
612
677
765
703
Счётчики для младших цифр 1 1 2 3 1 2 1 3 1 1
Страницы
- « первая
- ‹ предыдущая
- …
- 87
- 88
- 89
- 90
- 91
- …
- следующая ›
- последняя »
