Implementation of Pure Dual Pivot Quick Sort
Details
Details
Tests created in pawsort_tests
NEW DIFFERENTIAL REVISION
- Describe the changes in this new revision. # Included commits in branch T1225_DPQS: # 10a6eb30e684 T1225 - Implemented Pure Dual Pivot Quick Sort.
Diff Detail
Diff Detail
- Repository
- rP PawLIB
- Lint
Lint Not Applicable
Event Timeline
Comment Actions
Build is green
Building PawLIB on mpm-bionic-000929oczuya1 as build 535. Running test suite P-sB30.
See https://jenkins.mousepawmedia.net:8449/job/pawlib_build/535/ for more details.
Comment Actions
I am so out of touch with the sorting algorithms right now, it's not even funny. I'm going to have to refresh myself properly. Meanwhile, except for possibly switching from thirds to median-of-three for pivots, this is probably a good starting position.
Meanwhile, have we looked into the performance implications of std::iter_swap? I know we were debating about how to swap values some time back, but I can't remember the conclusions. (If I remember correctly, @iaroslavski was involved in that discussion...maybe we should get him involved again?)
| pawlib-source/include/pawlib/pawsort.hpp | ||
|---|---|---|
| 486–488 | One of the key components of the performance of DPQS comes down to these pivot points. See 653-662. | |
Comment Actions
By the way, I've added Sebastian Wild's thesis on Dual-Pivot Quicksort to the Files wiki. I suspect we'd both benefit from a perusal if we're going to achieve our goal.
Comment Actions
Although it can be improved, we can go ahead and just land this. The entire sorting library here will need refactor anyway, and this will be a good starting position for DPQS.
Comment Actions
There was a major error in this that I missed. I reimplemented your changes (for the most part). I reimplemented in rP14bd156133e9: Reimplement D263 (on behalf of lulu731)