Сравнение методов сортировки массива

Заканчивая наш обзор методов сортировки, мы попытаемся сравнить их эффективность. Как и раньше, n - число сортируемых элементов, а С и М - соответственно число необходимых сравнений ключей и число обменов. Для всех прямых методов сортировки можно дать точные аналитические формулы. Они приводятся В таблице. Столбцы Min, Аvg, Мах определяют соответственно минимальное, усредненное и максимальное по всем перестановкам из n элементов значения.

Для усовершенствованных методов нет сколько-либо осмысленных, простых и точных формул. Существенно, однако, что в случае сортировки Шелла вычислительные затраты составляют с * n1.2, а для HeapSort и QuickSort –

с * n * log n,

где с - соответствующие коэффициенты.

Эти формулы просто вводят грубую меру для производительности как функции n и позволяют разбить алгоритмы сортировки на примитивные, прямые методы (n2) и на усложненные или "логарифмические" методы (n * log( n)). Однако для практических целей полезно иметь некоторые экспериментальные данные, способные пролить свет на те коэффициенты с, которыми один метод отличается от другого. Более того, формулы не учитывают других затрат на вычисления, кроме сравнения ключей и переносов элементов, таких, например, как управление циклами и т. д. Ясно, что эти факторы во многом зависят от отдельной вычислительной системы, но, тем не менее, результаты экспериментов довольно информативны. Ниже, в таблице, собраны времена (в секундах) работы обсуждавшихся выше методов сортировки, реализованных в системе Модула-2 на персональной ЭВМ Lilith. Три столбца содержат времена сортировки уже упорядоченного массива, случайной перестановки и массива, расположенного в обратном порядке. Вначале приводятся цифры для 256 элементов, а ниже – для 2048. Чётко прослеживается отличие квадратичных методов от логарифмических.