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