Поразрядная сортировка

Cтраница 1

Поразрядная сортировка MSD требует выполнения по меньшей мере одного прохода сортировки методом подсчета индексных ключей, а подсчет индексных ключей предусматривает по меньшей мере два прохода по записям ( один для подсчета, другой для распределения), на что затрачивается по меньшей мере 2N шагов, еще два подхода предназначены для просмотра счетчиков ( один для их инициализации в 0 в начале, другой - для проверки, находятся ли подфайлы в конце), на что уходит по меньшей мере еще 2R шагов. [1]

Реализация поразрядной сортировки LSD, представленная в разделе 10.5, выполняет bytesword проходов по файлу. Увеличивая R, мы получаем эффективный метод сортировки для достаточно больших 7V при наличии дополнительного пространства памяти для размещения R счетчиков. Как отмечалось при доказательстве леммы 10.5, целесообразно выбирать R таким, чтобы значение InR ( число разрядов в байте) было примерно равно одной четвертой от размера слова, так чтобы поразрядная сортировка представляла собой четыре прохода сортировки методом подсчета индексных ключей. Проверяется каждый бит каждого ключа. Этот пример является прямой аналогией организационной архитектуры многих компьютеров: в одной из типичных организаций используется 32-разрядное слово, которое, в свою очередь, состоит из 8-разрядных байтов. Мы извлекаем из слов байты, а не биты, и этот подход позволяет достичь довольно высокой эффективности на многих типах компьютеров. Теперь каждый проход процедуры подсчета индексных ключей линеен, а поскольку их всего лишь четыре, то и вся сортировка линейна - вряд ли можно надеяться на что-либо лучшее, когда речь идет о сортировке. [2]

Функция поразрядной сортировки MSD выполняет разделение файла по первой цифре ключей, затем рекурсивно вызывает сама себя для обработки подфайлов, соответствующих каждому значению. На рис. 10.9 представлена структура этих рекурсивных вызовов для примера применения поразрядной сортировки MSD, показанного на рис. 10.8. Структура вызова соответствует многопутевому бинарному дереву, прямому обобщению древовидной структуры для двоичной быстрой сортировки, показанной на рис. 10.4. Каждый узел соответствует рекурсивному вызову сортировки MSD для некоторого подфайла. [3]

Лемма 10.3. Поразрядная сортировка MSD с основанием системы счисления R применительно к файлу размера N требует для выполнения по меньшей мере 2N 2R шагов. [4]

Пример сортировки поразрядным группированием. [5]

Рассмотрим пример поразрядной сортировки чисел, показанный на рис. 3.19, из которого совершенно ясно, как работает эта сортировка. В самом деле, это в точности тот же метод, какой используется на машинах для сортировки перфокарт. Однако три использовании его на цифровой вычислительной машине ( или при ленточных сортировках) этот метод имеет серьезные недостатки. [6]

Программный код поразрядной сортировки MSD фдктически мало чем отличается от программного кода быстрой сортировки с трехпутевым разбиением ( программа 9.5), отличия состоят в следующем: ( /) ссылки на ключи становятся ссылками на конкретные байты ключей, ( / /) текущий байт добавляется как параметр к рекурсивной служебной программе и ( / / /) рекурсивные вызовы для среднего подфайла перемещаются к следующему байту. Мы избегаем выполнять перемещения за пределы концов строк путем проверки, равно ли разделяющее значение 0, перед рекурсивными обращениями, которые обеспечивают переход к следующим байтам. Когда разделяющим значением является 0, левый подфайл пуст, средний подфайл соответствует ключам, которые, по определению программы, равны этому значению, а правый подфайл соответствует более длинным строкам, которые требуют дальнейшей обработки. [7]

Время выполнения поразрядной сортировки LSD при сортировке записей N с ключами, состоящими из w байтов, пропорционально Nw, поскольку соответствующий алгоритм производит w проходов по всем N ключам. Как показывает рис. 10.17, это свойство не зависит от природы входных данных. [8]

Чтобы реализовать поразрядную сортировку MSD, необходимо обобщить методы разделения массивов, которые мы рассматривали при изучении реализаций быстрой сортировки в разделе 10.7. Эти методы, в основу которых положено перемещение указателей с противоположных концов массива навстречу друг другу, так что они встречаются где-то посередине, работают хорошо при необходимости получения двух или трех разделов, но не допускают немедленного обобщения. К счастью, метод подсчета индексных ключей, который рассматривался в главе 6 для целей сортировки файлов с ключами, принимающих значения в узком диапазоне, в рассматриваемом случае подходит как нельзя лучше. При этом используются таблицы значений и вспомогательные массивы, на первом проходе массива подсчитывается количество повторений каждой цифры старшего разряда. Эти значения показывают, где окажутся точки разделения. [9]

В упрощенной форме поразрядная сортировка аналогична процессу механической сортировки перфокарт на ЭВМ. А соответствует числу значений, которые могут принимать символы ключей. А равно размеру алфавита, используемого для построения ключей. [10]

В худшем случае поразрядная сортировка выполняет проверку всех байтов и всех ключей. [11]

В основе алгоритмов поразрядной сортировки лежит абстрактная операция извлечь из ключа 7 - ю цифру. К счастью, в C существуют низкоуровневые операции, благодаря которым можно реализовать такие действия просто и эффективно. Этот факт очень важен, поскольку многие другие языки программирования ( например, Pascal), поощряя написание машинно-независимых программ, намеренно создают трудности в написании программ, которые зависят от способа представления чисел в конкретной машине. В таких языках достаточно трудно реализовать многие типы методы побитовых манипуляций, которые хорошо подходят для большинства компьютеров. [12]

Подход применительно к поразрядной сортировке получил широкое распространение в силу того, что он требует исключительно простых структур управления, а его базовые операции очень удобны для реализаций в машинном языке, который легко адаптируется к высокопроизводительным аппаратным средствам специального назначения. В такой среде наибольшее быстродействие, по-видимому, достигается при использовании полной поразрядной сортировки LSD. Если мы используем указатели, то чтобы воспользоваться поразрядной сортировкой LSD нам потребуется дополнительное пространство памяти для размещения N связей ( и R счетчиков), и эти затраты позволяют реализовать метод, который может сортировать файлы с произвольной организацией всего лишь за три-четыре прохода. [13]

Метод, альтернативный поразрядной сортировке, прсдусмпт-рииает просмотр CEIHTOB н нзлравлснии справа налево. На рис. 10.14 показано, как зааач-i сортировки трея & укиепных сю в мо-ж - ej быаь решена jia три прохода ни файлу - MEJ см чшия сортируем файл гто последней букве ( используя я: ы этой цели шгтл ппд - c Etra индексные к скэчсй), I TCM ETO срсл сн 6 у кис, и только лотом - по первой букве. [14]

Метод, альтернативный поразрядной сортировке, предусматривает просмотр байтов в направлении справа налево. На рис. 10.14 показано, как задача сортировки трехбуквенных слов может быть решена за три прохода по файлу. [15]

Страницы: 1 2 3 4