Comments 8
Что я могу сказать, обычный школьный квиксорт с массивами в 3 раза медленнее у меня получается. Оптимизированный без создания и объединения толпы новых массивов я не помню как делать и лень.
AS3, 50000 элементов. По пути был немного удивлен тем, что Array.sort в 12 раз медленнее.
Ничего больше особо не знаю об алгоритмах сортировки с университета, про оригинальность сказать не могу, но работает же. Сохраню чтоб не забыть.
Хотелось бы еще тестов и мыслей математиков получше чем я.
AS3, 50000 элементов. По пути был немного удивлен тем, что Array.sort в 12 раз медленнее.
Ничего больше особо не знаю об алгоритмах сортировки с университета, про оригинальность сказать не могу, но работает же. Сохраню чтоб не забыть.
Хотелось бы еще тестов и мыслей математиков получше чем я.
Ждал как минимум код с коментариями… Вполне бы можно оформить было ссылкой, а не топиком.
Оригинал здесь
У меня получились такие отношения количеств (приблизительно) на рандомных массивах до миллиона чисел:
сравнений «dual-pivot quicksort» к «classic quicksort»: ~1 ~1.05;
обменов «dual-pivot quicksort» к «classic quicksort»: ~2 ~2.5;
вызовов «classic quicksort» к «dual-pivot quicksort»: ~7.5 ~9.5.
Так что есть над чем подумать.
сравнений «dual-pivot quicksort» к «classic quicksort»: ~1 ~1.05;
обменов «dual-pivot quicksort» к «classic quicksort»: ~2 ~2.5;
вызовов «classic quicksort» к «dual-pivot quicksort»: ~7.5 ~9.5.
Так что есть над чем подумать.
А вот если привести оба алгоритма к одному виду, то количество вызовов вызовов «classic quicksort» к «dual-pivot quicksort» будет ~1.5. В этом случае преимущества приведённого алгоритма неясны :(
Несколько замечаний:
1) Ты, видимо, не читал «Algorithms in %langname%» Седжвика, он упоминает среди оптимизаций разбиение на три части, так не стоит лишать его чести в статье;
2) Собственно, самое главное достоинство и заодно причину повышенной скорости работы не написал: Обычный quicksort дико тормознут когда во входных данных много повторяющихся величин. Этот алгоритм их просто убирает из дальнейшего рассмотрения, что просто прекрасно.
1) Ты, видимо, не читал «Algorithms in %langname%» Седжвика, он упоминает среди оптимизаций разбиение на три части, так не стоит лишать его чести в статье;
2) Собственно, самое главное достоинство и заодно причину повышенной скорости работы не написал: Обычный quicksort дико тормознут когда во входных данных много повторяющихся величин. Этот алгоритм их просто убирает из дальнейшего рассмотрения, что просто прекрасно.
Портировал в Rubinius, тестирую. Выглядит неплохо :)
Похоже это частный случай вот этого открытого патента.
Only those users with full accounts are able to leave comments. Log in, please.
dual-pivot quicksort