Сравнение сроков и быстродействия

Ответ 1

TimSort очень оптимизирован для слияния, он стабилен и быстрее, чем старый mergesort.

при сравнении с quicksort он имеет два преимущества:

• Это невероятно быстро для почти упорядоченной последовательности данных (включая данные с обратной сортировкой);
• В худшем случае все еще O (N * LOG (N)).

Честно говоря, я не думаю, что 1-е преимущество, но это меня впечатлило.

Вот преимущества QuickSort.

• QuickSort - очень простая, даже очень настроенная реализация, мы можем записать свои коды pseduo в пределах 20 строк;
• QuickSort быстрее всего работает в большинстве случаев;
• Потребление памяти - LOG (N).

В настоящее время Java 7 SDK реализует timsort и новый вариант быстрой сортировки: т.е. Double Pivot QuickSort.

Если вам нужна стабильная сортировка, попробуйте timsort, иначе начните с быстрой сортировки.

Ответ 2

Более или менее это связано с тем, что Timsort является гибридным алгоритмом сортировки. Это означает, что в то время как два основных вида, которые он использует (сортировка Mergesort и Insertion), хуже, чем Quicksort для многих типов данных, Timsort использует их только тогда, когда это выгодно.

На более глубоком уровне, как утверждает Patrick87, быстрая сортировка является алгоритмом O (n ²) в худшем случае. Выбор хорошего центра не труден, но гарантированная быстрая сортировка O (n log n) достигается за счет обычно более медленной сортировки в среднем.

Подробнее о Timsort читайте в этом ответе и в сообщении в блоге. В основном это предполагает, что большая часть данных уже частично отсортирована, и создает "прогоны" отсортированных данных, которые обеспечивают эффективное слияние с использованием сортировки слиянием.

Ответ 3

Вообще говоря, quicksort - лучший алгоритм для примитивного массива. Это связано с локальностью памяти и кешем.

JDK7 использует массив TimSort для объекта. Объектный массив содержит только ссылку на объект. Сам объект хранится в куче. Чтобы сравнить объект, нам нужно прочитать объект из кучи. Это похоже на чтение из одной части кучи для одного объекта, а затем случайное чтение объекта из другой части кучи. Будет много промахов в кеше. Думаю, по этой причине местность памяти уже не важна. Возможно, именно поэтому JDK использует массив TimSort для Object вместо примитивного массива.

Это только моя догадка.

Ответ 4

Вот результаты тестов с моей машины (процессор i7-6700, 3.4 ГГц, Ubuntu 16.04, gcc 5.4.0, параметры: SIZE = 100000 и RUNS = 3):

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

Тестирование происходит из проекта Swenson sort, в котором он реализовал несколько алгоритмов сортировки в C. Предположительно, его реализации достаточно хороши, чтобы быть репрезентативными, но я их не исследовал.

Таким образом, вы действительно не можете сказать. Контрольные цифры сохраняют свою актуальность не более двух лет, а затем вы должны повторить их. Возможно, timsort победил qsort waaay еще в 2011 году, когда был задан вопрос, но времена изменились. Или qsort всегда был самым быстрым, но timsort превзошел его по неслучайным данным. Или код Свенсона не так хорош, и лучший программист переломил ситуацию в пользу тимсорта. Или, возможно, я отстой и не использовал правильный CFLAGS при компиляции кода. Или... Вы поняли.

Ответ 5

Tim Sort отлично подходит, если вам нужна сортировка с сохранением порядка или если вы сортируете сложный массив (сравнивая объекты на основе кучи), а не примитивный массив. Как упоминалось другими, быстрая сортировка значительно выигрывает от локальности данных и кэширования процессора для примитивных массивов.

Факт, что худший случай быстрой сортировки - O (n ^ 2), был поднят. К счастью, вы можете достичь O (n log n) времени худшего случая с быстрой сортировкой. Наихудший случай быстрой сортировки возникает, когда точка опоры является наименьшим или наибольшим значением, например, когда опорная точка является первым или последним элементом уже отсортированного массива.

Мы можем достигнуть O (N журнал N) в худшем случае быстрой сортировки путем установки опоры в среднее значение. Поскольку нахождение медианного значения может быть сделано за линейное время O (n). Поскольку O (n) + O (n log n) = O (n log n), это становится наихудшей временной сложностью.

На практике, однако, большинство реализаций обнаруживают, что достаточно случайного поворота, поэтому не ищите медианное значение.