Главные сортировки в Java 8
В Java 8, при попытке отсортировать массив элементов с помощью Arrays.sort, используются 2 основные оптимизированные сортировки: quick sort и merge sort. Первая выбирается для массивов из примитивов, а вторая в общем случае для любых объектов, для которых задан Comparator. Как гласит теория, оба алгоритма имеют одинаковую временную сложность O(n logn), но сортировка мержем гарантирует это, в то время как быстрая сортировка имеет такую оценку в среднем. Поэтому быстрая сортировка в java 8 сильно оптимизирована и включает в себя сразу 4 подхода, которые применяются в зависимости от характеристик массива. Над мерж-сортировкой так же достаточно сильно потрудились для оптимизации процесса мержа. Ниже приведены обобщенные описания идей, которые используются в обоих видах сортировок в Java8 и приведены иллюстрации улучшений алгоритмов по сравнению с классическими версиями. Само каноническое описание алгоритмов сортировок приводить не буду, т.к. предполагаю наличие этих знаний у читателя.
Merge Sort
Реализация сортировки расположена в java.util.TimSort и как гласит javadoc является адаптацией алгоритма мерж-сортировки Тима Питерса для питона. Его идея - продвинутая версия итеративного подхода сверху-вниз для мерж-сортировки.
Однако данный подход применяется не всегда. Когда размер массива небольшой, выгодней использовать сортировку вставками, что и делается, если размер массива меньше определенной константы (32 на момет написания статьи).
Бинарная сортировка вставками
Применяемая сортировка вставками так же оптимизирована. Ее идея состоит в том, чтобы использовать бинарный поиск в отсортированной части для того, чтобы обнаружить место, куда нужно вставить очередной элемент. После чего правая часть от этой позиции сдвигается вправо и на освободившееся место вставляется элемент.
Реализация merge sort
Если же массив больше порогового значения, то применяется собственно мерж-сортировка.
Для ее реализации используется идея нарезки массива на последовательности попеременно увеличивающихся и уменьшающихся последовательностей. Из этих последовательностей формируется массив возрастающих отрезков - для этого убывающие последовательности инвертируются. Таким образом каждый элемент массива - уже отсортированная часть исходного массива и остается только смержить между собой эти отрезки.
При этом, если длина отрезка слишком маленькая, то возрастающий отрезок формируется принудительно, получив очередную часть массива фиксированной длины и отсортировав ее с помощью все той же бинарной сортировки вставками.
Далее производится собственно процесс последовательного мержа отсортированных отрезков. При этом для оптимизации это производится не сразу, а при определенных условиях. До этого отрезки складываются в очередь и при разбалансировке условий производится мерж. Существенно это на принцип мержа не влияет, так что заострять внимание на этом не буду.
Во время мержа 2 отрезков на старте и при определенных условиях включается так называемый "галопирующий" проход. Его суть в том, чтобы пропустить элементы в левом или правом отрезках, которые соответственно заведомо меньше или больше наименьшего и наибольшего элементов в противоположном отрезке.
Далее производится собственно процесс последовательного мержа отсортированных отрезков. При этом для оптимизации это производится не сразу, а при определенных условиях. До этого отрезки складываются в очередь и при разбалансировке условий производится мерж. Существенно это на принцип мержа не влияет, так что заострять внимание на этом не буду.
Во время мержа 2 отрезков на старте и при определенных условиях включается так называемый "галопирующий" проход. Его суть в том, чтобы пропустить элементы в левом или правом отрезках, которые соответственно заведомо меньше или больше наименьшего и наибольшего элементов в противоположном отрезке.
Quick sort
Быстрая сортировка в java 8 устроена достаточно запутанно. Она содержит в себе не только собственно быструю сортировку, но и сортировку вставками и merge-сортировку. В зависимости от условий выбирается наиболее подходящий к случаю вариант.
Сортировка содержится в классе java.util.DualPivotQuicksort.
Сортировка содержится в классе java.util.DualPivotQuicksort.
Сортировка вставками
Как в случае с merge-сортировкой, при небольшом количестве элементов, выгодней использовать сортировку вставками. На момент написания статьи это 47 элементов.
Сама сортировка вставками делится на 2 варианта: левосторонняя и правосторонняя, в зависимости от того левую или правую часть массива относительно токена партицирования необходимо отсортировать.
Левосторонняя сортировка является традиционной реализацией алгоритма сортировки вставками без каких-либо улучшений.
Правосторонняя же использует 2 элемента для прохода влево на каждой итерации сортировки вставками, поэтому является более быстрой альтернативой традиционному методу.
Элементом a1 становится больший из 2 рабочих элементов. После выбора элементов производится поиск места вставки для a1. Затем продолжается поиск места для a2, начиная сразу за местом вставки a1. Таким образом экономится время на поиске места вставки.
Сама сортировка вставками делится на 2 варианта: левосторонняя и правосторонняя, в зависимости от того левую или правую часть массива относительно токена партицирования необходимо отсортировать.
Левосторонняя сортировка является традиционной реализацией алгоритма сортировки вставками без каких-либо улучшений.
Правосторонняя же использует 2 элемента для прохода влево на каждой итерации сортировки вставками, поэтому является более быстрой альтернативой традиционному методу.
Стандартное 3-way партицирование
Если же длина массива больше, чем порог сортировки вставками, но меньше чем определенный порог (286 элементов), то принудительно используется быстрая сортировка.
Как и в ситуации с сортировкой вставками, быстрая сортировка делится на 2 варианта: стандартное партицирование и двойное.
Под стандартным здесь понимается партицирование "голландский флаг", когда используется 1 токен, относительно которого производится партицирование на 3 части.
Двойное же подразумевает использование сразу 2 токенов и описание его будет приведено далее.
Используемый вариант определяется следующим образом. Длина массива делится примерно на 7 и выбираются 5 элементов массива относительно центра: 2 слева, 2 справа и центральный элемент. Эти элементы сортируются между собой в массиве. Если все они между собой различны, то используется двойное партицирование. Иначе, если есть хотя бы одна пара равных элементов, используется стандартное 3-way партицирование.
Стандартное партицирование является классической реализацией алгоритма - сортируемый массив разделяется на 3 части: меньше токена, равно токену и больше токена, а затем очередной обрабатываемый элемент массива перемещается в одну из этих частей.
Здесь k - очередной рабочий элемент, для которого необходимо решить, в какую часть его переместить.
После партицирования производится рекурсивная сортировка левой и правых частей. При этом для этих частей может использоваться сортировка вставками в зависимости от длины массива. И именно в этом месте для правой части используется правосторонний ее вариант.
Как и в ситуации с сортировкой вставками, быстрая сортировка делится на 2 варианта: стандартное партицирование и двойное.
Под стандартным здесь понимается партицирование "голландский флаг", когда используется 1 токен, относительно которого производится партицирование на 3 части.
Двойное же подразумевает использование сразу 2 токенов и описание его будет приведено далее.
Используемый вариант определяется следующим образом. Длина массива делится примерно на 7 и выбираются 5 элементов массива относительно центра: 2 слева, 2 справа и центральный элемент. Эти элементы сортируются между собой в массиве. Если все они между собой различны, то используется двойное партицирование. Иначе, если есть хотя бы одна пара равных элементов, используется стандартное 3-way партицирование.
Стандартное партицирование является классической реализацией алгоритма - сортируемый массив разделяется на 3 части: меньше токена, равно токену и больше токена, а затем очередной обрабатываемый элемент массива перемещается в одну из этих частей.
Здесь k - очередной рабочий элемент, для которого необходимо решить, в какую часть его переместить.
После партицирования производится рекурсивная сортировка левой и правых частей. При этом для этих частей может использоваться сортировка вставками в зависимости от длины массива. И именно в этом месте для правой части используется правосторонний ее вариант.
Двойное партицирование
При двойном партицировании в качестве токенов выбираются элементы e2 и e4. Далее производится похожее на стандартное партицирование с той лишь разницей, что в центральной части складываются не равные одному токену элементы, а которые >= e2 и <= e4.
После партицирования проводится рекурсивная сортировка левой и правой частей (которые <e2 и >e4 соответственно) аналогично процессу стандартного партицирования. Для средней части дополнительно производится анализ - если она достаточно большая (> 4/7 массива), то производится перенос равных e2 и e4 элементов по соответствующим сторонам в отрезке.
После этого производится сортировка средней незатронутой части - либо всего отрезка от e2 к e4, если переноса не было, либо оставшейся части после переноса между равными элементами e2 и e4.
После партицирования проводится рекурсивная сортировка левой и правой частей (которые <e2 и >e4 соответственно) аналогично процессу стандартного партицирования. Для средней части дополнительно производится анализ - если она достаточно большая (> 4/7 массива), то производится перенос равных e2 и e4 элементов по соответствующим сторонам в отрезке.
После этого производится сортировка средней незатронутой части - либо всего отрезка от e2 к e4, если переноса не было, либо оставшейся части после переноса между равными элементами e2 и e4.
Merge sort
В случае, если длина массива больше порога применения быстрой сортировки (286 элементов), проверяются определенные условия на возможность применения merge-сортировки.
Для этого массив нарезают на возрастающие отрезки подобным образом, как в главе о merge-сортировке выше за исключением того, что не производится принудительная сортировка отрезка при малой длине. Если окажется, что в одном из отрезков присутствует больше определенного количества (33 на данных момент) одинаковых элементов или отрезков слишком много (больше 67), то производится переход к быстрой сортировке.
В противном случае начинается процесс последовательного мержа отрезков между собой. Он имеет гораздо более простой алгоритм, чем тот который используется в merge-сортировке выше и особо ничем не отличается от классического описания процесса мержа.
Для этого массив нарезают на возрастающие отрезки подобным образом, как в главе о merge-сортировке выше за исключением того, что не производится принудительная сортировка отрезка при малой длине. Если окажется, что в одном из отрезков присутствует больше определенного количества (33 на данных момент) одинаковых элементов или отрезков слишком много (больше 67), то производится переход к быстрой сортировке.
В противном случае начинается процесс последовательного мержа отрезков между собой. Он имеет гораздо более простой алгоритм, чем тот который используется в merge-сортировке выше и особо ничем не отличается от классического описания процесса мержа.
Комментарии