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