<<
>>

2.4 Сравнение методов

В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации: Устойчивость.

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

<< | >>
Источник: Томас Ниман. Сортировка и поиск: Рецептурный справочник. 1995

Еще по теме 2.4 Сравнение методов: