Сравнение методов
В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации:
· Устойчивость. Напомним, что устойчивая сортировка не меняет взаимного расположения элементов с равными ключами. Сортировка вставками – единственный из рассмотренных алгоритмов, обладающих этим свойством.
· Память. Сортировке на месте не требуется дополнительная память. Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке требуется стек для организации рекурсии. Однако, требуемое этому алгоритму место можно сильно уменьшить, повозившись с алгоритмом.
· Время. Время, нужное для сортировки наших данных, легко становится астрономическим (см. таблицу 1.1). Таблица 2.2 позволяет сравнить временные затраты каждого из алгоритмов по количеству исполняемых операторов..
| Method | statements | average time | worst-case time
|
| insertion sort | 9 | O(n2) | O(n2) |
| shell sort | 17 | O(n1.25) | O(n1.5) |
| quicksort | 21 | O(n lg n) | O(n2) |
Таблица 2.2:Сравнение методов сортировки
· Время, затраченное каждым из алгоритмов на сортировку случайного набора данных, представлено в таблице 2.3.
| count | insertion | shell | quicksort |
| 16 | 39 ms | 45 ms | 51 ms |
| 256 | 4,969 ms | 1,230 ms | 911 ms |
| 4,096 | 1.315 sec | .033 sec | .020 sec |
| 65,536 | 416.437 sec | 1.254 sec | .461 sec |
Таблица 2.3: Время сортировки
Вероятность иметь ссылку уровня 2 равна j. В общем, количество ссылок на узел равно
 |
· Время. Алгоритм должен быть эффективным. Это особенно важно, когда ожидаются большие объемы данных. В таблице 3.2 сравниваются времена поиска для каждого алгоритма. Обратите внимание на то, что наихудшие случаи для хеш-таблиц и разделенных списков чрезвычайно маловероятны. Экспериментальные данные описаны ниже.
· Простота. Если алгоритм короток и прост, при его реализации и/или использовании ошибки будут допущены с меньшей вероятностью. Кроме того, это облегчает проблемы сопровождения программ. Количества операторов, исполняемых в каждом алгоритме, также содержатся в таблице 3.2.
|
метод |
операторы |
среднее время |
время в худшем случае |
|
хеш-таблицы |
26 |
O(1) |
O(n) |
|
несбалансированные деревья |
41 |
O(lg n) |
O(n) |
|
красно-черные деревья |
120 |
O(lg n) |
O(lg n) |
|
разделенные списки |
55 |
O(lg n) |
O(n) |
В таблице 3.3 приведены времена, требуемые для вставки, поиска и удаления 65536 (216) случайных элементов. В этих экспериментах размер хеш-таблицы равнялся10009, для разделенных списков допускалось до 16 уровней ссылок. Конечно, в реальных ситуациях времена могут отличаться от приведенных здесь, однако, таблица дает достаточно информации для выбора подходящего алгоритма.
|
метод |
вставка |
поиск |
удаление |
|
хеш-таблицы |
18 |
8 |
10 |
|
несбалансированные деревья |
37 |
17 |
26 |
|
красно-черные деревья |
40 |
16 |
37 |
|
разделенные списки |
48 |
31 |
35 |
В таблице 3.4 приведены средние времена поиска для двух случаев: случайных данных, и упорядоченных, значения которых поступали в возрастающем порядке. Упорядоченные данные являются наихудшим случаем для несбалансированных деревьев, поскольку дерево вырождается в обычный односвязный список.
Приведены времена для “одиночного” поиска. Если бы нам понадобилось найти все 65536 элементов, то красно-черныму дереву понадобилось бы 6 секунд, а несбалансированному – около 1 часа.
|
Элементов |
хеш-таблицы |
несбалансированные деревья |
красно-черные деревья |
разделенные
списки |
|
|
16 |
4 |
3 |
2 |
5 |
|
|
случайные |
256 |
3 |
4 |
4 |
9 |
|
данные |
4,096 |
3 |
7 |
6 |
12 |
|
65,536 |
8 |
17 |
16 |
31 |
|
|
16 |
3 |
4 |
2 |
4 |
|
|
упорядоченные |
256 |
3 |
47 |
4 |
7 |
|
данные |
4,096 |
3 |
1,033 |
6 |
11 |
|
65,536 |
7 |
55,019 |
9 |
15 |
