Pull to refresh

dual-pivot quicksort

Algorithms
Улучшенный алгоритм quicksort: iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

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

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

В PDF-е автор алгоритма привдит более детализированное описание алгоритма и имплементацию на java.
Tags:algorithmsortcomputer science
Hubs: Algorithms
Total votes 21: ↑13 and ↓8 +5
Views8.4K

Comments 8

Only those users with full accounts are able to leave comments. Log in, please.

Popular right now

Middle/Senior ML Engineer
from 250,000 ₽GradientМоскваRemote job
Data Science Cloud Administrator (remote)
from 200,000 to 300,000 ₽Bergmann InfotechRemote job
Data Science Cloud Engineer (remote)
from 200,000 to 300,000 ₽Bergmann InfotechRemote job
Data Scientist / Специалист по Data Science
to 250,000 ₽ЮвелирочкаМоскваRemote job
Team-lead Data Science со специализацией в Rec-Sys
from 210,000 to 320,000 ₽СберМосква