Pull to refresh

dual-pivot quicksort

Reading time 1 min
Views 11K
Улучшенный алгоритм quicksort: iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

Краткое описание:
Обычный quicksort делит массив на два отрезка, выбрав случайный элемент P. Потом сортирует массив так, чтобы все элементы меньше P попали в первый отрезок, а остальные — во второй. Затем алгоритм рекурсивно повторяется на первом и на втором отрезках.

Dual-pivot quicksort делит массив на три отрезка, вместо двух. В результате количество операций перемещения элементов массива существенно сокращается.

В PDF-е автор алгоритма привдит более детализированное описание алгоритма и имплементацию на java.
Tags:
Hubs:
+5
Comments 8
Comments Comments 8

Articles