Алгоритмы / dual-pivot quicksort
Суббота, Суббота, Сентябрь 12, 2009 - 17:05 - Новости с Хабра
Улучшенный алгоритм quicksort: iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
Краткое описание:
Обычный quicksort делит массив на два отрезка, выбрав случайный элемент P. Потом сортирует массив так, чтобы все элементы меньше P попали в первый отрезок, а остальные — во второй. Затем алгоритм рекурсивно повторяется на первом и на втором отрезках.
Dual-pivot quicksort делит массив на три отрезка, вместо двух. В результате количество операций перемещения элементов массива существенно сокращается.
В PDF-е автор алгоритма привдит более детализированное описание алгоритма и имплементацию на java.
AD: