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.
Так что есть над чем подумать.
UFO just landed and posted this here
Портировал в Rubinius, тестирую. Выглядит неплохо :)
Похоже это частный случай вот этого открытого патента.
Sign up to leave a comment.
dual-pivot quicksort