Какая разница в быстром сортировке и быстрой сортировке двойного шарнира?

Ответ 1

Я нахожу это в документе Java.

Алгоритм сортировки - это двойная поворотная быстрая сортировка Владимира Ярославского, Джона Бентли и Джошуа Блоха. Этот алгоритм обеспечивает производительность O (n log (n)) для многих наборов данных, которые приводят к ухудшению квадратичной производительности других быстрых сортировок, и, как правило, быстрее, чем традиционные реализации (с одним поворотом) быстрой сортировки.

Затем я нахожу это в результатах поиска Google. Вот алгоритм быстрой сортировки:

1. Выберите элемент, называемый сводной, из массива.
2. Переупорядочьте массив таким образом, чтобы все элементы, меньшие, чем сводка, располагались перед сводкой, а все элементы, большие, чем сводка, следовали за ней (равные значения могут идти в любом случае). После этого разбиения элемент поворота находится в своем окончательном положении.
3. Рекурсивно сортировать вложенный массив меньших элементов и вложенный массив больших элементов.

Для сравнения: быстрая сортировка с двумя точками поворота:

()

1. Для небольших массивов (длина <17) используйте алгоритм сортировки вставками.
2. Выберите два поворотных элемента P1 и P2. Например, мы можем получить первый элемент a [left] как P1 и последний элемент a [right] как P2.
3. P1 должен быть меньше P2, иначе они меняются местами. Итак, есть следующие части:
   • часть я с индексами слева + 1 до L – 1 с элементами, которые меньше, чем P1,
   • часть II с индексами от L до K – 1 с элементами, которые больше или равны P1 и меньше или равны P2,
   • часть III с индексами от G + 1 вправо – 1 с элементами больше, чем P2,
   • часть IV содержит остальные элементы, которые нужно исследовать с индексами от K до G.
4. Следующий элемент a [K] из части IV сравнивается с двумя осями P1 и P2 и помещается в соответствующую часть I, II или III.
5. Указатели L, K и G меняются в соответствующих направлениях.
6. Шаги 4 - 5 повторяются, пока K ≤ G.
7. Поворотный элемент P1 заменен последним элементом из части I, поворотный элемент P2 заменен первым элементом из части III.
8. Шаги 1 - 7 повторяются рекурсивно для каждой части I, части II и части III.

Ответ 2

Для тех, кто заинтересован, посмотрите, как они реализовали этот алгоритм в Java:

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%2Cint%5B%5D%2Cint%2Cint%29

Как указано в источнике:

"Сортирует заданный диапазон массива с использованием заданного массива массива рабочего пространства, если возможно, для слияния

Алгоритм обеспечивает производительность O (n log (n)) во многих наборах данных, которые приводят к снижению производительности в быстродействующих сегментах до квадратичной производительности и обычно быстрее, чем традиционные (однопоточные) реализации Quicksort.

Ответ 3

Я просто хочу добавить, что с точки зрения алгоритма (т.е. Стоимость учитывает только количество сравнений и перестановок), 2-pivot quicksort и 3-pivot quicksort не лучше, чем классическая quicksort (которая использует 1 pivot), если нет хуже. Однако на практике они работают быстрее, поскольку используют преимущества современной компьютерной архитектуры. В частности, их количество кешей меньше. Поэтому, если мы удалим все кэши и останемся только процессор и основная память, в моем понимании, 2/3-пивотная быстрая сортировка хуже, чем классическая быстрая сортировка.

Ссылки: 3-pivot Quicksort: https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 Анализ того, почему они работают лучше классической Quicksort: https://arxiv.org/pdf/1412.0193v1.pdf Полная и не слишком подробная информация: https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf