QuickSort с двумя опорными элементами

[alexey_rom]

Владимир Ярославский придумал новый вариант быстрой сортировки, делающий меньше перестановок и более быстрый на практике. Детали здесь.

Comments

[lionet]

Что-то я чувствую боян древний какой-то:

http://video.google.com/videoplay?docid=-1031789501179533828&hl=en#

[alexey_rom]

Да нет. На 43:06 Бентли показывает как раз [ = p | < p | > p | = p ] как достижение. Именно этот вариант сейчас используется в JDK (насколько я понимаю) и сравнение производительности сделано именно с ним.

А что сам Бентли думает насчёт этого варианта, сказано там, куда я дал ссылку, под From: Jon Bentley

[lionet]

The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.

Ах, да. Невнимательно прочитал. Сначала прочитал описание, затем вспомнил, что где-то я что-то похожее видел, затем запостил видео. Оказалось, видео от Бентли самого же.

[deni_ok]

avva пишет:
Спасибо за наводку на Седжвика. Я стал копать глубже - его докторская диссертация была полностью посвящена детальному анализу квиксорта и его вариаций. Он разбирает алгоритм, идентичный варианту Ярославского, и приходит к выводу, что он требует в несколько раз больше обменов, чем стандартный алгоритм. Я не знаю пока, кто из них прав...

[alexey_rom]

Интересно. Посмотрим...

[dp_maxime]

А не частный ли это случай вот этого: http://www.freepatentsonline.com/y2007/0088699.html ?