пересылок элементов. Для всех трех простых методов copin-ровки можно дать замкнутые аналитические формулы. Онп приведены в табл. 2.8. Заголовки столбцов Min, Мах, Средн. определяют соответственно минимумы, максимумы и ожидаемые средние значения для всех п! перестановок п элементов.

Таблица 2.8. Сравнение простых методов сортировки

Для усовершенствовавдых методов нет достаточно простых и точных формул. Все, что можно сказать,- это что стоимость вычислений равна Ci-n} в случае сортировки Шелла и Cj-n-logn в случаях пирамидальной и быстрой сортировок.

Эти формулы дают лишь приблизительную оценку эффективности как функции от п; они допускают классификацию алгоритмов сортировки на простые (п^) и усовершенствованные, или логарифмические (n-logn). Однако для практических целей полезно иметь некоторые экспериментальные данные, которые могут пролить свет на коэффициенты с позволяющие проводить дальнейшую оценку различных методов. Кроме того, в этих формулах не учитываются затраты на другие операции, отличные от сравнений ключей и пересылок элементов, такие, как управление циклами и т. д. Разумеется, эти факторы в какой-то степени зависят от конкретных систем, но тем не менее некоторый пример экспериментально полученных данных является информативным. В табл. 2.9 приведено время (в миллисекундах), которое затратила система Паскаль на вычислительной машине CDC 6400 на выполнение сортировки описанными здесь методами. В трех столбцах указано время, потребовавшееся для сортировки уже рассортированного массива, случайной перестановки и массива с обратным порядком элементов. Левов

ГаЗлица 2.9. Время выполнения программ сортировки

1 См. разд. 2.3.1.

ЧИСЛО В каждой колонке дано для массива из 256 элементов, а правое--для 512 элементов. Эти данные демонстрируют явное отличие методов от методов n-logn. Примечательны следующие моменты:

1. Преимущество сортировки бинарными включениями по сравнению с сортировкой простыми включениями действительно ничтожно, а в случае уже имеющегося порядка вообще отсутствует.

2. Сортировка методом пузырька определенно является наи-худщей среди всех сравниваемых методов. Ее улучшенная версия - шейкер-сортировка все-таки хуже, чем сортировка простыми включениями и простым выбором (кроме патологического случая сортировки уже рассортированного массива).

8. Быстрая сортировка превосходит пирамидальную сортировку в отношении 2 к 3. Она сортирует массив с элементами, расположенными в обратном порядке практически

так же, как уже рассортированный.

Следует добавить, что эти данные были получены при сортировке элементов, состоящих только из ключа без сопутствующей информации. Это - не слишком реалистичное допущение; в табл. 2.10 показано, как влияет увеличение раз- ера элементов на скорость работы программ. В выбранном Примере сопутствующие данные занимают в 7 раз больше Памяти, чем ключ. Левое число в каждой колонке показывает. Ьремя, нужное для сортировки записей без сопутствующих

2. Сортировка

Таблица 2.10. Время выполнения программ сортировки (Ключи с сопутствующей информацией)

Упорядоченный массив

Случайный массив

Упорядоченный в обратном порядке массив

Простые включения Бинарные включения Простой выбор Метод пузырька Метод пузырька с

ограничением Шейкер-сортировка Сортировка Шелла Пирамидальная

сортировка

Быстрая сортировка- Сортировка слиянием*

12 46

56 76

489 547

540 610

58 186

116 264

-&i-55-

99 196

366 1129

373 1105

509 607

1026 3212

1104 3237

961 3071

127 373

-60-

246 102 195

704 2150

662 2070

695 1430

492 5599

1645 5762

1619 5757

157 435

104 37 99

227 75 187

*) См. разд. 2.3.1.

данных, правое - отражает сортировку с сопутствующими данными; п = 256. Обратите внимание на следующие детали:

1. Сортировка простым выбором дает существенный выигрыш и оказывается лучшим из простых методов.

2. Сортировка методом пузырька по-прежнему является наихудшим методом (она еще больше сдала свои позиции!), и лишь ее усовершенствование , называемое шейкер-сортировкой, еще чуть хуже в случае массива с обратным порядком.

3. Быстрая сортировка даже укрепила свою позицию в качестве самого быстрого метода и оказалась действительно лучшим алгоритмом сортировки.

2.3. сортировка последовательных файлов

2.3.1. Простое слияние

К сожалению, алгоритмы сортировки, рассмотренные в предыдущей главе, неприменимы, если сортируемые данные не помещаются в оперативной памяти, а, например, расположены на внешнем запоминающем устройстве с последовательным доступом, таком, как магнитная лента. В этом случае мы описываем данные как (последовательный) файл, который характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному элементу. Это - строгое ограничение по сравнению с возможностями, которые дает массив, и поэтому здесь приходится применять другие методы сортировки. Основной метод -это сортировка