Cтраница 2
Было установлена to сгронэьсиштельность поразрядной сортировки чожно существенно у & еличить, расе митр и вазе йд повременно Солее одного разряда, То же самое справедливо н в отношении поразрядною Енжска: исследуя одновременно по г разряде н скорость поиска можно увеличить н г раз. Однако, существует скрыта н опасность. Лроблсчэ заключается и том, что одновременное рассмотрение г разрядов соответствует использованию узлов лерсыа с Д2Г снн. [16]
Интервальная сортировка - аналог поразрядной сортировки - так же, как быстрая сортировка, является аналогом двоичной поразрядной сортировки. Распределение основано на значении всего ключа, принадлежащего определенному интервалу. Этот метод можно использовать и как внутренний, и как внешний с лентами или дисками. Особенно он интересен во внешнем окружении в качестве альтернативы внешнему слиянию. Этот метод должен разделять входные данные по нескольким бункерам, каждый из которых содержит отдельный интервал ключей. Начальные группы расщепляются затем на все меньшие и меньшие до тех пор, пока список не станет упорядоченным или акая-нибудь сравнительная сортировка не упорядочит последние маленькие группы. [17]
Всего лишь одна стадия поразрядной сортировки MSD почти полностью решает задачу упорядочения, как показывает рассматриваемый пример файла произвольной организации, состоящий из 8-разрядных целых чисел. Первая стадия поразрядной сортировки MSD по двум старшим разрядам ( слева) делит исходный файл на четыре подфайла. На следующей стадии каждый такой подфайл делится на четыре подфайла. Поразрядная сортировка MSD по трем старшим разрядам ( справа) делит файл на восемь подфайлов за один проход, на котором также выполняются распределение и подсчет. На следующем уровне каждый из этих подфайлов снова разбивается на восемь частей, при этом в каждой такой части содержатся всего лишь несколько элементов. [18]
Другой естественный путь реализации поразрядной сортировки MSD предполагает использование связных списков. [19]
Предлагаемое представление рекурсивной структуры поразрядной сортировки MSD более компактно, чем представление на рис. 10.9. Каждый узел этого дерева помечен значением ( I - 1) - й цифры конкретного ключа, где - это расстояние от узла до корня. Каждый путь от корня до нижнего уровня дерева соответствует конкретному ключу; если теперь соединить метки узлов в одно слово, получим соответствующий ключ. Данное дерево соответствует представленному на 10.7 примеру поразрядной сортировки MSD слов из трех букв. [20]
Это дерево соответствует действию рекурсивной поразрядной сортировки MSD, реализованной в программе 10.2, на примере упорядочения совокупности двухбуквенных слов методом поразрядной сортировки MSD, представленного на рис. 10.8. Если файл принимает размер 0 или 1, рекурсивные вызовы отсутствуют. В остальных случаях имеет место 26 вызовов: один на каждое возможное значение текущего байта. [21]
Алгоритм сортировки, аналогичный поразрядной сортировке ( R. [22]
Подход ( грименнтельно к поразрядной сортировке получил широкое распространение в CRT у того, что он требует исключительно простых структур управления, а его базовые операции очень удойны для реализаций а машинном яшке, который легко шдагттирустся к высокопроизводительным аппаратным средствам специального назначения, В такой среде наибольшее быстродействие, но-пилим ому достигается при ис-мо. LSD, Если мы используем указатели, то чтобы попользоваться норгирклкой сортировкой LSD нам потребуется дополнительное пространство памяти для размещения / V евшей ( и Д счетчиков), и эти затраты позволяют ревизовать метод, который может сортировать файлы с произвольной ирга ни злцие и всего лишь за три-четыре прохода. [23]
Было установлено, что производительность поразрядной сортировки можно существенно увеличить, рассматривая одновременно более одного разряда. То же самое справедливо и в отношении поразрядного поиска: исследуя одновременно по г разрядов, скорость поиска можно увеличить в г раз. Однако, существует скрытая опасность, вынуждающая применять эту идею более осторожно, чем в случае поразрядной сортировки. Проблема заключается в том, что одновременное рассмотрение г разрядов соответствует использованию узлов дерева с R2r связями, а это может приводить к значительным напрасным затратам памяти для неиспользуемых связей. [24]
Ключевое условие для понимания сути поразрядной сортировки состоит в признании того, что ( /) компьютеры в общем случае ориентированы на обработку групп битов, называемых машинными словами, которые в свою очередь часто объединяются в небольшие фрагменты, называемые байтами; ( И) ключи сортировки обычно также организуются в последовательности байтов, ( in) короткие последовательности байтов могут также служить индексами массивов или машинными адресами. Поэтому нам будет удобно работать со следующими абстракциями. [25]
Данная диаграмма служит иллюстрацией использования поразрядной сортировки справа налево, разряд за разрядом, применительно к рассматривавшемуся выше файлу учебному ключей. [26]
Другими словами, различные виды поразрядной сортировки суть линейные сортировки в том смысле, что затрачиваемое на нее время в большинстве случаев пропорционально количеству цифр во входных данных. Этот факт непосредственно следует из анализа программ: ни одна из цифр не проверяется дважды. [27]
На рис. 10.6 показан пример поразрядной сортировки MSD на произвольных перестановках целых чисел. В отличие от двоичной быстрой сортировки этот алгоритм может привести файл в относительный порядок достаточно быстро, даже после первого разделения, если значение основания системы счисления достаточно велико. [28]
Фактически метод z - буфера осуществляет поразрядную сортировку по х и у, а затем сортировку по z, требуя всего одного сравнения для каждого пиксела каждой грани. [29]
В зависимости от контекста ключом в поразрядной сортировке может быть слово или строка. [30]