|
Страница 4 из 60
Оценка алгоритмов сортировки Для каждого метода сортировки имеется много алгоритмов. Каж-
дый алгоритм имеет свои достоинства, но в целом оценка алгоритма
сортировки зависит от ответов, которые будут получены на следую-
щие вопросы:
- с какой средней скоростью этот алгоритм сортирует информа-
цию?;
- какова скорость для лучшего случая и для худшего случсая?;
- поведение алгоритма является естественным или является не-
естественным?;
- выполняется ли перестановка элементов для одинаковых клю-
чей?
Для конкретного алгоритма большое значение имеет скорость
сортировки. Скорость, с которой массив может быть упорядочен,
прямо зависит от числа сравнений и числа необходимых операций об-
мена, причем операции обмена занимают большее время. Ниже в этой
главе будет показано, что для некоторых алгоритмов время сорти-
ровки зависит экспоненциально от числа элементов, а для других
алгоритмов это время находится в логарифмической зависимости от
числа элементов сортировки.
Время работы алгоритма для лучшего и худшего случаев важно
учитывать, когда ожидается их частое появление. Часто сортировка
имеет хорошую среднюю скорость, но очень плохую скорость для худ-
шего случая, и наоборот.
Считается поведение алгоритма сортировки естественным, если
время сортировки наименьшее при упорядоченном списке элементов,
время сортировки увеличивается при менее упорядоченном списке
элементов и время сортировки становится наихудшим, когда список
элементов упорядочен в обратном порядке. Время сортировки зависит
от числа операций сравнения и операций обмена.
Для того, чтобы понять важность перегруппировки элементов с
одинаковыми ключами сортировки, представим базу данных, которая
упорядочена по основному ключу и дополнительному ключу. /Напри-
мер, список почтовых отправлений с почтовым индексом в качестве
основного ключа и фамилией в качестве дополнительного ключа в
рамках одного почтового индекса/. Когда новый адрес добавляется в
список и список вновь сортируется, вам не требуется перестановка
дополнительных ключей. Для обеспечения этого сортировка не должна
выполнять операции обмена для основных ключей с одинаковыми зна-
чениями.
В следующих разделах приводятся алгоритмы сортировки каждого
класса и анализируется их эффективность. Каждая программа сорти-
ровки использует два типа данных, определенных пользователем, ко-
торые определяются следующим образом:
type
DataItem = char;
DataArray = array [1..80] of DataItem;
Следовательно, для изменения используемых в сортировках ти-
пов данных требуется изменить только эти два определения типов.
Размерность массива выбрана произвольно и вы можете при необходи-
мости их изменить. |