Введение в информационные системы. Брюхомицкий Ю.А. - 117 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

117
Для сортировки методом Шелла последовательности из N элементов
требуется около log
2
N проходов. Для примера, показанного на рис. 8.5, расчет-
ное число проходов получается равным 3–4, фактическое – 3.
Число сравнений существенно зависит от шага. Для предложенной
Шеллом последовательности шагов (N/2, N/4, N/8 и т.д.) приближенную оценку
числа сравнений производят по формуле Nlog
2
N.
Факторы, учитываемые при выборе метода сортировки. Рассмотренные
методы внутренней сортировки могут иметь различные модификации, различ-
ные процедуры, реализующие тот или иной метод или его модификацию. На-
пример, метод обмена («пузырька») имеет ряд модификаций; метод вставок
своим названием объединяет, по существу, целую группу методов сортировки,
основанных на последовательной вставке новых элементов
в упорядоченную
последовательность. Из этой группы рассмотрен только метод линейных вста-
вок, наиболее полно иллюстрирующий принцип метода. Кроме метода линей-
ной вставки существуют методы центрированной и двоичной вставок.
Существует класс методов сортировки, в которых используется древо-
видное представление данных. Так, в разделе 5 описан метод смешанного обхо-
да бинарного дерева, при
котором получаемая последовательность является
отсортированной по возрастанию значений ключей. На этом основан один из
методов сортировки, использующий древовидное представление данных. Суть
метода заключается в том, что по исходной неупорядоченной последовательно-
сти записей, имеющих некоторые значения ключа, строится бинарное дерево и
затем осуществляется смешанный обход полученного дерева. В результате чте-
ния содержимого
узлов бинарного дерева в процессе такого обхода получается
последовательность признаков, отсортированная по возрастанию значения клю-
чевого признака.
Помимо метода сортировки, в котором используется обход бинарного
дерева, существует широкий класс так называемых турнирных сортировок,
также использующих древовидное представление данных.
Известно большое количество модификаций методов внешней сорти-
ровки, в которых используется принцип
слияния.
Более полно вопросы, связанные с сортировкой данных, рассмотрены, в
частности, в /7/.
Внутренняя сортировка данных обычно не требует длительного време-
ни, и в большинстве случаев приемлем любой из рассмотренных методов, а
также их модификация или комбинация. При этом на каждом этапе сортировки,
в зависимости от величины сортируемого массива, используется метод, обеспе
-
чивающий минимальное число сравнений.
Однако иногда возникает необходимость выбора или разработки метода
сортировки, удовлетворяющего определенным требованиям. Такая ситуация
может возникнуть при жестких ограничениях на свободный объем оперативной
памяти. Возможны также какие-то необычные сочетания характеристик сорти-
руемых данных, делающих малопригодными обычные методы. В этих случаях

Страницы