Метод - сортировка
Cтраница 4
На первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. И действительно, процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для больших же n Heapsort очень эффективна; чем больше п, тем лучше она работает. Она даже становится сравнимой с сортировкой Шелла. [46]
Естественно, не может не интересовать проблема, какой метод сортировки выбрать для конкретного приложения: пирамидальную сортировку, быструю сортировку или сортировку слиянием. Выбор между пирамидальной сортировкой и сортировкой слиянием сводится к выбору между неустойчивой сортировкой ( см. упражнение 9.28) и сортировкой, которая использует дополнительный объем памяти; выбор между пирамидальной сортировкой и быстрой сортировкой сводится к выбору между средним быстродействием сортировки и быстродействием, обеспечиваемым в наихудшем случае. В свое время мы достаточно хорошо потрудились над совершенствованием внутренних циклов быстрой сортировки и сортировки слиянием; решение этих вопросов применительно к сортирующим деревьям мы предоставляем в упражнениях, сопровождающих настоящую главу. Речь отнюдь не идет о повышении производительности пирамидальной сортировки до уровня, превосходящего быструю сортировку, что, собственно говоря, показано посредством эмпирических данных, приведенных в табл. 9.2. Тем не менее, специалисты, изучающие проблему быстрой сортировки на собственных машинах, найдут эти данные поучительными. Как обычно, различные характерные особенности конкретных машин и систем программирования могут сыграть важную роль. Например, быстрая сортировка и сортировка слиянием обладают свойством локальности, которое дает им определенные преимущества на некоторых типах вычислительных машин. Когда операции сравнения становятся недопустимо дорогостоящими, версия Флойда подходит лучше других, поскольку в такого рода ситуациях она становится чуть ли не оптимальной, если принимать во внимание только время выполнения и стоимость используемого пространства памяти. [48]
Для того чтобы сократить количество сравнений, любой из эффективных сравнительных внутренних методов сортировки предполагает некоторую нелинейную структуру или разбиение сортируемого списка. Конкретной структурой, которая используется в широком классе методов сортировки, является дерево. В этой главе будут введены основные понятия о деревьях и древовидных структурах, необходимые для обсуждения методов сортировки, которые вводятся в последующих главах. [49]
Если ключи являются действительными числами, то принципиально возможно применение метода сортировки по основанию системы счисления. В случае ограниченной точности также при использовании метода сортировки по основанию системы счисления т оказывается слишком большим. Однако если известно, что распределение значений ключей относительно равномерно, то возможно применение следующего метода, близкого к методу сортировки по основанию системы счисления. [50]
Формирование составов на вытяжке должно производиться, как правило, методом скоростной сортировки вагонов: серийными, много-группными толчками или поточной сортировкой вагонов, для чего вытяжки должны иметь специальный профиль, а к составителю должны быть прикреплены башмачники. Формирование поездов должно начинаться еще в процессе накопления вагонов путем под-формирования их в группы по методу составителя Кожухаря. [51]
В следующих разделах рассматриваются факторы, не относящиеся к основным свойствам методов сортировки. [52]
Предположите, что вставки в динамическую таблицу символов размера TV реализуются методом сортировки вставками, но для выполнения операции search используется бинарный поиск. Предположите, что поиск выполняется в 1000 раз чаще вставки. [53]
Наиболее простым методом сортировки, предполагающим многократные распределения и слияния отрезков, является метод сортировки сбалансированным слиянием. [54]
Конечно, все перечисленные варианты задачи выбора можно решить, используя любой из методов полной сортировки имен, изложенных в разд. Но при этом мь получаем гораздо больше информации, чем требуется, так что следует поискать лучшие пути. [55]
Страницы: 1 2 3 4