dual-pivot quicksort
Improved quicksort algorithm: iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
Short description:
A regular quicksort divides an array into two segments, selecting a random element P. Then sorts the array so that all elements less than P fall into the first segment, and the rest into the second. Then the algorithm is recursively repeated on the first and second segments.
Dual-pivot quicksort divides an array into three segments, instead of two. As a result, the number of operations to move the elements of the array is significantly reduced.
')
In PDF, the author of the algorithm will provide a more detailed description of the algorithm and implementation on java.
Short description:
A regular quicksort divides an array into two segments, selecting a random element P. Then sorts the array so that all elements less than P fall into the first segment, and the rest into the second. Then the algorithm is recursively repeated on the first and second segments.
Dual-pivot quicksort divides an array into three segments, instead of two. As a result, the number of operations to move the elements of the array is significantly reduced.
')
In PDF, the author of the algorithm will provide a more detailed description of the algorithm and implementation on java.
Source: https://habr.com/ru/post/69424/
All Articles