dual-pivot quicksort

Все истинно гениальное очень просто.

http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Не прошло и 50 лет.

  • kayru

    Идея ведь совсем на поверхности была.
    Почему раньше про это никто не подумал? =\

  • look4awhile

    интересно, а 3 и более pivot-а кто-нибудь уже попробовал?
    какой-нибудь N-pivot? адаптивно N от размера, скажем?

  • kayru

    2 look4awhile: По-моему, дополнительные операции сравнения перевесят сохраненные операции обмена.

  • CreatorCray

    Сбацал бы кто performance тест на C++ со сравнением хотяб с std::sort

  • kayru

    2CreatorCray: приведенный в пдфе код практически без изменений компилируется как с++

  • kayru

    http://www.everfall.com/paste/id.php?5srxcy7g5hcb

    std::sort: 252436
    dual-pivot: 185687
    ratio: 0.735581

    vs2008, intel c2d e6850

    В среднем прирост колебется в пределах 20-25%

  • CreatorCray

    2kayru: блин, точно… :)

    В общем получается что на DWORDах новый qsort делает старый в раза 1.5-2
    Но с ростом размера сортируемых объектов новый начинает ацки сливать.

  • Pingback: highly professional scums » Blog Archive » Bubblesort, кеши и быстродействие()