Сравнение методов внутренней сортировки
Для рассмотренных в начале этой части простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). Таблица 2.10 содержит данные, приводимые в книге Никласа Вирта.
Таблица 2.10. Характеристики простых методов сортировки
| Min | Avg | Max | |
| Прямое включение |
C = n-1 M = 2x(n-1) |
(n2 + n - 2)/4 (n2 - 9n - 10)/4 |
(n2 -n)/2 - 1 (n2 -3n - 4)/2 |
| Прямой выбор |
C = (n2 - n)/2 M = 3x(n-1) |
(n2 - n)/2 nx(ln n + 0.57) |
(n2 - n)/2 n2/4 + 3x(n-1) |
| Прямой обмен |
C = (n2 - n)/2 M = 0 |
(n2 - n)/2 (n2 - n)x0.75 |
(n2 - n)/2 (n2 - n)x1.5 |
Для оценок сложности усовершенствованных методов сортировки точных формул нет. Известно лишь, что для сортировки методом Шелла порядок C и M есть O(n(1.2)), а для методов Quicksort, Heapsort и сортировки со слиянием - O(n?log n). Однако результаты экспериментов показывают, что Quicksort показывает результаты в 2-3 раза лучшие, чем Heapsort (в таблице 2.11 приводится выборка результатов из таблицы, опубликованной в книге Вирта; результаты получены при прогоне программ, написанных на языке Модула-2). Видимо, по этой причине именно Quicksort обычно используется в стандартных утилитах сортировки (в частности, в утилите sort, поставляемой с операционной системой UNIX).
Таблица 2.11. Время работы программ сортировки
| Упорядоченный массив | Случайный массив | В обратном порядке | |
| n = 256 | |||
|
Heapsort Quicksort Сортировка со слиянием |
0.20 0.20 0.20 |
0.08 0.12 0.08 |
0.18 0.18 0.18 |
| n = 2048 | |||
|
Heapsort Quicksort Сортировка со слиянием |
2.32 2.22 2.12 |
0.72 1.22 0.76 |
1.98 2.06 1.98 |
