CodeNet / Приложения / Алгоритмы / Поиск. Строки и последовательности / Сортировка и поиск: Рецептурный справочник
CodeNet / Приложения / Алгоритмы / Сортировка / Сортировка и поиск: Рецептурный справочник
CodeNet / Приложения / Алгоритмы / Сортировка / Сортировка и поиск: Рецептурный справочник
Сравнение методов
В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации:
- Устойчивость. Напомним, что устойчивая сортировка не меняет взаимного расположения элементов с равными ключами. Сортировка вставками - единственный из рассмотренных алгоритмов, обладающих этим свойством.
- Память. Сортировке на месте не требуется дополнительная память. Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке требуется стек для организации рекурсии. Однако, требуемое этому алгоритму место можно сильно уменьшить, повозившись с алгоритмом.
- Время. Время, нужное для сортировки наших данных, легко становится астрономическим (см. таблицу 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) |
| кол-во
элементов |
вставки | Шелл | 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 |