Содержание

пятница, 10 февраля 2012 г.

Сортировка в Java

Я уверен, что абсолютное большинство java программистов знают как отсортировать коллекцию или массив средствами JDK в одну строчку. А вот в том, что все знают как внутри будет просиходит сортировка и от чего это зависит, я уже не очень уверен. Тем более в java 7 эта логика очень сильно поменялась. В этом топика я расскажу о принципиальном различии между сортировкой объектов и примитивов, о различии сортировок в зависимости от длины массива и типа примитивов, а так же упомяну о способах поддержания коллекций в сортировоном виде.

Сортировка объектов
Основное отличие сортировки массива объектов от массива примитивов заключается в том, что для первого используется стабильный алгоритм, т.е. порядок объектов в массиве не меняется для равных элементов. В java 6 для этого используется простейшая реализация сортировки слиянием (mergesort), т.е. алгоритм требует N/2 дополнительной памяти и дает сложность O(N*lgN) как в худшем случае, так и в среднем.

В java 7 для сотировки объектов используется ваирация алгоритма timsort. Он дает сложность много лучше чем O(N*lgN) на частично упорядоченных массивах и гарантирует слжоность классического mergesort для произвольного массива. Если массив практически полностью упорядочен, то потребует всего около N сравнений и небольшое константное дополнительное пространство. Тогда как на произвольном массивве потребуется гарантированно не больше N/2 дополнительного пространства, как для обычного mergesort.

И в той и в другой версии java, если длина массива меньше семи, то используется сортировка вставками (insert sort), которая не требует дополнительного места, дает в худшем случае слжоность O(N^2), зато на упорядоченных массивах показывает завидную производительность.
Сортировка примитивов
Так как равные примитивы неразличимы между собой, то для них не обязательно ограничиваться стабильными алгоритмами в общем случае. В java 6 для любого типа массива примитивов используется быстрая сортировка (quicksort), которая в среднем дает сложность O(N*lgN), которая хоть ассимптотически и совпадает со сложностью сортировки слиянием (mergesort), но все же на практике ее заметно обходит. Однако в худжем случае сложность падает до O(N^2). Для массивов длины меньше семи используется уже упомянутая раньше сортировка вставками (insert sort).

В jаva 7 разброс алгоритмов значительно богаче как в зависимости от типа примитива, так и в зависимости от размера массива. Так для массива байтов длины меньше 30 исползуется сортировка вставками (insert sort), для всех же остальных используется сортировка подсчетом (count sort). Последняя дает стабильную линейную сложность O(N). Она позволяет обойти нижнуюю границу O(N*lgN), тем что при сортировке не требует сравнений.

Для примитивов типа char и short сортировка подсчетом (count sort) исползуется уже только для массивов длинее 3200 символов, ведь, в этом случае уже потребуется 256К дополнительной памяти. Для массивов короче 47 символов используется соритровка вставкой (insert sort). Для всех же остальных массивов применяется сортировка слиянием с элементами быстрой сортировки и сортировки вставками.

В случае, кодга массив содержит int, float или double, для массивов с количеством элементов меньше 47 используется сортировка вставкаи, для массивов от 47 до 286 применяется быстрая сортировка (quick sort). Причем используется dual-pivot вариация этого алгоритма, т.е. каждый раз массив делиться не на две части, а на три. Не смотря на то, что строгая математика показывается, что данный подход дает большую сложность, нежели классическая быстрая сортировка, в итогде был выбран именно этот алгоритм, как выдававший лучшие результаты для JVM. Для всех остальных размеров массивов, исползуется сортировка слиянием с эементами быстрой соритровки и сортировкой вставками.
Сортировка коллекций
В java есть утилитный метод, который позволяет отсортировать любой ArrayList или LinkedList: java.util.Collections.sort(List list). Данный метод скалдывает все элементы в массив объектов, сортирует используя метод, описанный в секции про массивы, и складывает обратно в огигинальный список. Таким образом для сортировки списков может потребоваться вплоть до 150% дополнительного пространства.

Если вам надо поддерживать вашу коллекцию в сортированном виде, то конечно можно при каждой вствке исползовать бинарный поиск, но есть более удобные методы. Например, можно использовать класс java.util.TreeSet, который будет хранить ваши элементы в двоичном дереве поиска. При итерировании по данной коллеции вы будете иметь упорядоченную коллекцию. Если же у вас элемены в коллекции могут дублироваться, то множество здесь уже не подойдет. В зависимости от задачи можно взять java.util.PriorityQueue, основанный на бинарной куче. Правда он уже вам не даст итерирования по упорядоченной колекции, а будет лиш отдавать наибольший элмент из содержащихся. Если же вам нужно именно итерирование по упорядоченной, часто изменяемой коллекции с дублирующимися элементами, то можно обратить свой взор на com.google.common.collect.TreeMultiset. Его хоть и нет в JDK, но находиться он все же в довольно популярной и зарекомендовавшей себя библиотеке.