Лекции по информатике (984119), страница 22
Текст из файла (страница 22)
В результате общее число сравнений равно и, 1оя и, а общее число 7> !ОЯО 7> обменов 6 . Несмотря на то что вероятность выбора медианы только 17>и произ> водительность быстрой сортировки при случайном выборе зернового элемента ухуд>лается лишь в постоянное число раз 2!и 2. Недостатками быстрой сортировки являются низкая производительность при небольших п, но этим грегпат все усовершенствованные методы !54].
Для обработки случаев малых п в усовершенствованные сортировки вклк>чан>т один из простых методов. Проще всего это делать для рекурсивной сортировки Хоара. Небольшое, но эффективное усовершенствование возможно при выборе зернового элемента как среднего из трех случайно взятых. Наконец, в случае явного дисбаланса величин элементов к сортировке большей половины применяют пирамидальный алгоритм. И именно та,кая комбинированная стратегия используется в алгоритме вогг() библиотеки ВТЕ. Интересно, что для поиска медианы существует эффективный алгоритм, очень похожий на быструн> сортировку и, как ни странно, двоичный поиск.
На первом этапе выбирается зерновой элемент и происходит разделение относительно него. Местом медианы в отсортированной последовательности б>улет п)2. Если зерно ~~~~~ на ~~~~ц~~ А ( и,'2, 352 то медиана находится справа от него, в противном случае слева. Применив разделение к болыпей части, либо найдем медиану, либо получим следующий отрезок для ее рекурсивного поиска. Цена этого процесса линейная: и и п+ — + — +...+1=2п. 2 4 Однако в самой неблагоприятной ситуации множество кандидатов уменьшается только на 1, а число сравнений оценивается 0(п ).
Впрочем, применив вышеописанные способы выбора разделяющего элемента, можно свести к нулю вероятность возникновения такой ситуации. Еще одно усовершенствование быстрой сортировки связано с оценкой размера стека для хранения границ отложенных участков. В самом неблагопрятном случае, когда в стек заносятся одпоэлементпые участки, его размер оценивается в и элементов. Если же заносить в стек «более длинную часть» и продолжать разделение более короткой части, размер стека может быть ограничен 1оя п. Тогда в программу нерекурсивной сортировки Хоара должны быгь внесены следующие изменения: 11 ) — 1.
< К вЂ” 1 1Ьеп Ьен1п Ы ~»с К СЬеп Ьеи1п 1' занесение в сгпек запроса, на, сортировку правой части у $.Ь: -1; с.К: — К; Рпа111зсэ Ф); епс1; К: ); 1' Продолзкение сорпиаровкп левой части / епс1 е1ае Ъеи1п 11 Ь «: ) СЬеп Ьец1п 1' занесение в стек запроса на сорпшровку левой части 1 с . 1.: 1.; 1.К: — ); Рцз1т(зс, с); епс1; Ь: — 1: 1' Продолжение сортировки правой части 3 епс1; 6.2.3 Сравнение методов внутренней сортировки Теперь, когда нами изучены все методы внутренней сортировки, можно произвести их тоталысое сравнение. Во-первых, прямые методы сортировки имеют точные оценки [541. Усовершенствованные методы не имеют сколько-нибудь простых и точных формул сложностной оценки.
Для сортировки Шелла затраты составляют О!и'+~), а для пирамидальной и быстрой 0(п !о8п), Эти оценки позволян~т разбить все сортировки на примитивные, прямые, квадратичные методы со сложностью 0(пэ) и улу ппснныс или линеарифмическис Г)(п !о8 и). В реальных случаях на коэффициенты этих оценок могут влиять архитектурные факторы (ускорение пересылок и,'или сравнений аппаратными средствами либо оптимизирующими компиляторами) и форма и местонахождение (резидентные, ... ) ключей (простые или составные). Прежде, чем давать сравнительную эмпирическую оценку всех сортировок, напомним соответствующие порядки роста величин-степеней 2. и !ОК и и, !сап и Сортировка Шелла Линейный Дихотомия Быстрые сортировки поиск Двоичное дерево (Дейкстра, Флойд, Хоар) Простые сортировки Поскольку полу ~ить точные оценки для всех сортировок затруднительно, представляют интерес результаты вычислительного эксперимента, проведенного Н.
Виртом на мик- роЭБМ 1л!!Гп с микропрограммной поддержкой языка Модула 2 (М-код) для массива данных из 2048 элементов со скалярным ключом: Упорядоченный Случайный Обратный порядок Времена, приведенные в этой таблице, во-псрвых. свидетельствуют о колоссальной разнице квадратичных и линеарифмических методов уже на массиве из 2048 элементов 1 16 256 4,.096 65 о36 1,048.,576 16,.777,216 Вставка Двоичная вставка, Выборка Пузырьковая Шсйкерная Шелла, Пирамидальная 1ладкая Быстрая Быстрая перекуре.
Слияние 0 12 16 20 0,22 1,.16 58.,18 80,18 0.,16 0,80 2,32 о,227 0,.72 0.72 1.98 0 64 2,048 49,152 1,048,565 20,969,520 402,653, 184 50,74 37,66 58.,34 128,.84 104,.44 7,08 2,22 2.,227 1,22 1,32 2,06 1 1.024 32.,768 1,.028,.576 33 554 432 1,073,741,.824 1 256 Г) 5,536 16,777,216 4,294,967,296 1,099,511,627,776 281.,474,976,710,.656 103,80 76,06 73,46 178,66 187,36 12,34 2,12 2,127 0,76 0,80 1,98 (а это всего лишь число ст)пгснтов, ежегодно оканчивающих МЛИ!). Во-вторых,.
° двоичная вставка по сравнению с простой почти ничего не дает, а в случае упорядоченного массива даже получается отрицательный эффект; ° пузырьковая сортировка определенно наихудшая из всех сравниваемых, ее усовершенствованная шейкерная версия все равно проигрывает почти всем методам; ° быстрая сортировка в 2 -3 раза лучше пирамидальной, но уступает ее гладкой разновидности на почти упорядоченных последовательностях.
Гладкая сортировка ТОИ02005. Сортировка Лукашевича (1984). Для упорядочения строк небольшой длины они отображаются на вещественный тип, после (его сортировка ускоряется за счет гораздо более бы(трого сравнения клк)ч(.й. Незадачш иноходи новы(. ((люч)( склеи~аю~с~ (на 32-битном геа1).
Но все равно идеи Рабина-Карпа живут и поосждают! Цифровая(разрядная) сортировка. 6.2.4 Внешние сортировки Рассмотренные нами алгоритмы Внутренней сорт)(ровки сугц(.стВ(,'ннО испОльзоВали прямой доступ к элементами массива и возможность их быстрой п('.рестановки за постоянное время 01(1). Аппаратная поддержка прямого доступа обеспечивается устройствами основной ((оперативной) памяти ЭВМ. Несмотря на ее гигабайтные сегодняшние размеры, эта память остается дефицитной, поскольку запросы и потребности практических задач растут опережающими темпами. Многие задачи сортировки работают с настолько большими массивами данных, что никакая существенная часть их не помещается в оперативной памяти.
Среди устройств внешней памяти существуют магнитные диски, также называемые устройствами прял(ого (про звольного) доступа, но анализ их конструкции свидетельствует о существенной зависимости времени доступа от местонахождения искомого элемента данных. Мгновенно (электронно) осуществляется только переключение между головками одного цилиндра. Остальные движения: поступательное перемещение с цилиндра на цилиндр и вращательное движение - подвод сектора к головке электромеханические и осуществляются хоть и за не(х)льп)ое, но за линейное Время. И именно это линейное время доминирует в оценках времени внешних сортировок на этих дисках.
Алгоритмы внутренних сортировок становятся либо неприменимыми, либо должны быть модифицированы. Итак, последовательный характер доступа так или иначе доминирует на всех внешних устройствах и налагает весьма сильное ограничение, вынуждая)щее нас использовать другие методы сортировки. Характерным методом внешней сортировки является метод слияния. Под слиянием понимается подобное слиянию двух рек объединение двух или более входных последовательностей в одну-единственную упорядоченную выходнун) последовательность с помощью повторяющегося выбора из доступных в данный момент резидентных (буферных) элементов.
Слияние — очень простая и быстрая операция, которую можно приспособить для задач внешней сортировки. Начнем рассмотрение слияния с частного случая слияния упорлдоче)()(ыг последо()ате>(ш((>с))(ей. Сначала надо сравнить резидентные буферные переменные этих последовательностей (Тор(а,) или 1ч 1) и запомнить из какой входной последовательности посту- пило минимальное значение. Далее необходимо извлечь (прочитать и удалить из буфера!) соответствующую компоненту этой последовательности и поместить ес в выходную последовательность. Повторяя этот процесс до окончания входных потоков данных, за линейное время (2п операций) мы получим отсортированную последовательность.
В этом случае дополнительной памяти (рабочих лент) не требуется, а производительность сравнима с такими же отзывчивыми на входную упорядоченность внутренними сортировками как сортировка вставкой или гладкая сортировка. Идея слияния может быть п1эименена и к неупорядоченным входным данным, при этом их упорядоченность будет постепенно возрастать в процессе нескольких слияний подпоследовательностей исходных данных до их полной упорядоченности. Рассмотрим идею сортировки простым слиянием: 1.
последовательность а разбивается на 2 половины 5 и с; часги 6 и с алпепюгпсл; при этом одиночные э ьехюнгы из разных частей об1эазуют упорядоченные пары в выходной последовательности, т. е. первым в ней оказывается меныпий иэ двух первых элементов этих частей; 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
