Comments 18
Помню, как восхищенно читал про dual-pivot и пытался его реализовать для Go. Но в итоге реализовал обычный, т.к. с интерфейсом, основанным на Less многовато сравнений выходило, а вокруг каверзных паттернов все равно ворк-эраунды приходилось строить.
И всё равно продолжаю восхищаться.
используется Dual-Pivot Quicksort, предложенный мною вместе с Джоном Бентли и Джошем Блоком в 2009 году
Неужто прям автором? 😁
Видимо, да.
Да, именно так. В javadoc это тоже отражено.
Очень интересная статья. Читать было захватывающе.
Узнал много нового, спасибо.
А еще хороший пример, того, что имя выбранное согласно тому, что код делает, со временем устаревает.
Интересная статья. Я вот никогда не понимал, почему стандартные либы для Джавы (и даже С/С++) не имеют реализации поразрядной сортировки (radix sort), которая имеет (уникальную) линейную сложность и на не очень длинных ключах легко бьет все остальные методы.
Сейчас открыт Pull Request на добавление Radix Sort в сортировку, надеюсь, что изменения будут скоро интегрированы.
Везде пишут, что поразрядная сортировка эффективна на целочисленных ключах. Однако, понятно, что любой ключ можно представить как множество "разрядов". Известны ли попытки применения ее к нецелочисленным ключам? Хотя бы к float и string? Интуитивно кажется, что при правильном "разбиении ключа на разряды", результаты должны быть очень неплохими.
На самом деле, если нет NaN, float легко сортировать как целые числа. Если только положительные, то вообще телодвижений делать не нужно.
Строки по первым символам тоже можно разбросать на мелкие бакеты, и потом применить обычную сортировку внутри бакетов. Правда, это если первые символы хоть как-то отличаются: массив интернетовских ссылок весь будет начинаться с http:// и https://
Поразрядную сортировку легко применить к вещественным числам. Сначала все NaN'ы перемещаются в конец и обрабатываются отрицательные нули (точно такие же как и в случае быстрой сортировки), далее с помощью небольшой магии получаем целочисленные ключи и сортируем их как обычные 32-битные числа (если float) или 64-битные (если double). Открытый Pull Request на добавление Radix Sort включает и float / double.
вот такая мысль есть
теоретически, если удастся разбить на одном проходе массив
на части 1/2, 1/4, 1/8, 1/16 ...
это уменьшит время вдвое
Можно применить сортировку вставками, но тогда мы получим 10 сравнений. Есть более эффективный способ для работы с небольшими количествами элементов — сети сортировки. Для 5 элементов они дают 9 сравнений.
Сортировка вставками отсортирует 5 элементов максимум за 8 сравнений, в среднем за 7.
Максим, добрый день!
Спасибо за ваш комментарий! Количество сравнений будет зависеть от того, как мы реализуем сортировку вставками для пяти элементов.
Если раскрывать циклы в классической сортировке вставками, то в наихудшем случае понадобится 10 сравнений. В сортировке вставками на каждой итерации проверяем вставляемый элемент с каждым элементом из уже отсортированной части, пока не найдем его место.
Для первого элемента нам сравнивать ничего не нужно,
для второго элемента понадобится одно сравнение с первым,
третий элемент нужно будет сравнить с первыми двумя,
...
итого 1 + 2 + 3 + 4 = 10 максимум сравнений.
В среднем будет меньше, но гарантировано 8 сравнений не хватит (если мы идем по шагам классической сортировки вставками с последовательным сравнением). Если же искать место вставляемого элемента бинарным поиском, то получим 8 сравнений (1 + 2 + 2 + 3), про которые вы упоминали.
Вообще говоря, достаточно 7 сравнений (5! = 125 < 128 = 2^7), когда мы идем по бинарному дереву и отсекаем половину вариантов перестановок. Но если писать такой код в лоб, то он получается на две страницы и очень некрасивый.
Поэтому используется гибрид с максимальным количеством сравнений, равным 8: сначала запускается сеть сортировки для 4 элементов (5 сравнений) и потом могут идти максимально 3 сравнения. В среднем же, будет около 7 сравнений. Чуть хуже, чем в теоретически лучшем варианте, но лишние действия принесены в жертву ради элегантности и краткости кода. В гибридном варианте меньше и количество обменов по сравнению с сортировкой вставками.
Как это реализовано, можно посмотреть здесь https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java, строки 321-339.
Удивительная история развития сортировки в JDK