Cтраница 4
Когда какой-либо из них может быть использован, выбор между быстрой сортировкой и различными алгоритмами поразрядной сортировки ( и имеющие к ним отношение различные версии быстрой сортировки. В табл. 10.1 и 10.2 приводятся эмпирические результаты, свидетельствующие в пользу вывода о том, что линейная или сублинейная зависимость рабочих характеристик, которые мы рассматривали применительно к различным приложениям поразрядной сортировки, делают эти методы сортировок привлекательными для различных подходящих приложений. [46]
После того, как установлена важность свойства устойчивости, нетрудно дать формулировку доказательства того, что поразрядная сортировка LSD работает: мы знаем, что после упорядочения ключей по / замыкающим байтам ( при сохранении устойчивости) любые два ключа в файле появляются в нужном порядке ( в соответствии с просмотренными на текущий момент разрядами) либо благодаря тому, что первые из / замыкающих байтов отличны друг от друга, в подобном случае сортировка по этому байту расставила их в соответствующем порядке, или если первые из / замыкающих байтов совпадают, они уже упорядочены нужным образом в силу свойства устойчивости. [47]
В обычных средах программирования внутренний цикла программы, реализующей подсчет индексных ключей, который служит основой поразрядных сортировок, содержит намного большее число инструкций, чем внутренние циклы быстрой сортировки или сортировки слиянием. Из этого свойства программных реализаций следует, что описанные выше сублинейные методы во многих случаях не могут, вопреки нашим ожиданиям, обладать таким же быстродействием как, скажем, быстрая сортировка. [48]
Дополнительное пространство памяти для вспомогательного массива не представляют собой сколь-нибудь серьезной проблемы в условиях многочисленных приложений поразрядной сортировки применительно к длинным ключам или записям, поскольку для этих типов данных успешно применяется сортировка по указателю. [49]
В обычных средах программирования внутренний цикла программы, рсализую-шсй подсчет индексных ключей, который служит основой поразрядных сортировок, содержит намного большее число инструкции h чем внутренние циклы быстрой сор-гироики или сортировки слиянием. Из этого свойства программных реализуй и и следует, что списанные выше сублинейные методы во многих случаях не могут, вопреки нашим ожиданиям, обладать таким же быстродействием как, скажем, быстрая сортировка. [50]
Если на вашем компьютере функционирует подходящая система виртуальной памяти, выполните эмпирическое сравнение быстрой сортировки, поразрядной сортировки MSD, поразрядной сортировки LSD и пирамидальной сортировки для сверхбольшого файла. Выберите файл максимально возможных в вашей системе размеров. [51]
Интервальная сортировка - аналог поразрядной сортировки - так же, как быстрая сортировка, является аналогом двоичной поразрядной сортировки. Распределение основано на значении всего ключа, принадлежащего определенному интервалу. Этот метод можно использовать и как внутренний, и как внешний с лентами или дисками. Особенно он интересен во внешнем окружении в качестве альтернативы внешнему слиянию. Этот метод должен разделять входные данные по нескольким бункерам, каждый из которых содержит отдельный интервал ключей. Начальные группы расщепляются затем на все меньшие и меньшие до тех пор, пока список не станет упорядоченным или акая-нибудь сравнительная сортировка не упорядочит последние маленькие группы. [52]
Алгоритмы общего назначения, такие как быстрая сортировка, нашли на практике более широкое применение, чем поразрядная сортировка, поскольку они могут адаптироваться к более широкому диапазону приложений. Например, один из широко распространенных способов установления интерфейса со служебной программой сортировки заключается в том, чтобы клиент сам выбирал функцию сравнения. Это программное средство не только годится в ситуации, когда клиент может воспользоваться специальными сведениями о сложных ключах с целью реализации быстрого сравнения, но также позволяет выполнять сортировку, используя отношения порядка, которые вообще могут обходиться без ключей. [53]
Алгоритмы общего назначения, такие как быстрая сортировка, нашли на практике более широкое [ рцменсние4 чем поразрядная сортировка, поскольку они могут адаптироваться к более широкому диапазону приложений. [54]