Сравнение методов
В данном разделе мы сравним описанные алгоритмы сортировки: вставками,
Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор
алгоритма в каждой конкретной ситуации:
-
Устойчивость. Напомним, что устойчивая сортировка не меняет взаимного
расположения элементов с равными ключами. Сортировка вставками - единственный
из рассмотренных алгоритмов, обладающих этим свойством.
-
Память. Сортировке на месте не требуется дополнительная память.
Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке
требуется стек для организации рекурсии. Однако, требуемое этому алгоритму
место можно сильно уменьшить, повозившись с алгоритмом.
- Время. Время, нужное для сортировки наших данных, легко становится
астрономическим (см. таблицу 1.1). Таблица 2.2
позволяет сравнить временные затраты каждого из алгоритмов по количеству исполняемых
операторов. Время, затраченное каждым из алгоритмов на сортировку случайного
набора данных, представлено в таблице 2.3.
-
Простота. Количество операторов, выполняемых каждым алгоритмом,
приведено в таблице 2.2. Более простые алгоритмы вызывают меньше ошибок
при программировании.
| метод |
кол-во
операторов |
ср. время |
время для
наихудшего
случая |
сортировка
вставками |
9 |
O(n2) |
O(n2) |
сортировка
Шелла |
17 |
O(n1.25) |
O(n1.5) |
быстрая
сортировка |
21 |
O(n lg n) |
O(n2) |
Таблица 2.2:Сравнение методов сортировки
кол-во
элементов |
вставки |
Шелл |
quicksort |
| 16 |
39 µs |
45 µs |
51 µs |
| 256 |
4,969 µs |
1,230 µs |
911 µs |
| 4,096 |
1.315 sec |
.033 sec |
.020 sec |
| 65,536 |
416.437 sec |
1.254 sec |
.461 sec |
Таблица 2.3: Время сортировки