Collections sort java как работает

Arrays, Collections: Алгоритмический минимум

Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники Oracle JDK 7.80 (UPD: добавлена ссылка).

В самом обобщенном виде результат изучения представлен на рисунке. Подробности — в основном тексте.

Рисунок 1. Методы Arrays, Collections и реализуемые ими алгоритмы

Первое, что поразило меня в алгоритмах, реализованных в Arrays и Collections — то, что их можно буквально по пальцам пересчитать — по большому счету, это два алгоритма сортировки и один алгоритм поиска.

Второе — то, что сортировка списков «под капотом» использует сортировку массивов.

Третье — то, что один из алгоритмов сортировки портирован с python.

Алгоритм быстрой сортировки с двумя опорными элементами разработан нашим соотечественником Владимиром Ярославским и реализован при содействии Джона Бентли и Джошуа Блоха.

Алгоритм сортировки слиянием, который является основным для сортировки массивов ссылочных типов, буквально назван по имени своего создателя Tim Peters — TimSort. Этот алгоритм был адаптирован Джошуа Блохом с алгоритма сортировки списков, реализованном на python Тимом Петерсом.

Кратко излагая результаты, стоит отметить, что:

1. Можно условно выделить три слоя методов:
   • Методы API
   • Методы базовых (основных) алгоритмов
   • Методы (блоки) дополнительных алгоритмов
2. Основных алгоритмов используется три. Два алгоритма сортировки: быстрая сортировка, сортировка слиянием. Один алгоритм поиска: бинарный поиск.
3. Для оптимизации «основные» алгоритмы заменяются на более подходящие в данный момент “дополнительные” алгоритмы (полный список алгоритмов и условий переключения приведен в конце)
4. Для определения того, какой из «дополнительных» алгоритмов будет задействован, могут использоваться:
   • сигнатуры методов (типы аргументов, булевы переменные)
   • флаги VM
   • пороговые значения длины массива/списка, хранящиеся в приватных переменных классов

Итак, для того, чтобы выяснить, какие основные и дополнительные алгоритмы используются в пакете util, нужно разобрать реализацию 4-х методов из API Collections и API Arrays.

Таблица 1. API Arrays vs API Collections

Метод	Arrays API	Collections API
Sort method	Arrays.sort	Collections.sort
Search method	Arrays.binarySearch	Collections.binarySearch

Arrays.sort

Массивы примитивных типов

Основной алгоритм сортировки для массивов примитивных типов в Arrays — быстрая сортировка. Для реализации этой сортировки выделен финальный класс DualPivotQuickSort, который предоставляет публичные методы sort для сортировки массивов всех примитивных типов данных. Методы Arrays API вызывают эти методы и пробрасывают в них ссылку на массив. Если требуется отсортировать определенный диапазон массива, то передаются еще и индексы начала и конца диапазона.

Временная сложность алгоритма быстрой сортировки в лучшем случае и в среднем случае составляет O(n log n). В некоторых случаях (например, на малых массивах) алгоритм быстрой сортировки обладает не лучшей производительностью, деградирует до квадратичной сложности. Поэтому имеет смысл вместо него применять другие алгоритмы, которые в общем случае проигрывают, но в конкретных случаях могут дать выигрыш. В качестве дополнительных алгоритмов были выбраны сортировка вставками, “обычная” быстрая сортировка (с одной опорной точкой), сортировка подсчетом.

Инженеры Oracle эмпирическим путем вычислили оптимальные размерности массивов для задействования каждого дополнительного алгоритма сортировки. Эти значения записаны в приватных полях класса DualPivotQuickSort. Для наглядности я свел их в таблицу 2.

Таблица 2. Дополнительные алгоритмы в DualPivotQuickSort.sort

Типы данных	Размер массива, n	Предпочитаемый алгоритм	Временная сложность в лучшем случае
int, long, short, char, float, double	n < 47	insertion sort, pair insertion sort	O(n)
int, long, short, char, float, double	n < 286	quick sort	O(n log n)
byte	29 < n	counting sort	O(n+k)
short, char	3200 < n	counting sort	O(n+k)

В теле методов DualPivotQuickSort.sort производятся проверки на длину массива, и в зависимости от результата применяется либо основной, либо дополнительный алгоритм.

Массивы примитивных типов. Выбор алгоритма и булев параметр leftmost

Параметр leftmost при необходимости передается в метод sort и показывает, является ли указанная часть самой левой в диапазоне. Если да, то применяется алгоритм “обычной” сортировки вставками. Если нет, то применяется парная сортировка вставками.

Еще одно объяснение о выборе дополнительных алгоритмов можно почитать
здесь.

Массивы ссылочных типов

Для массивов ссылочных типов в качестве основного предусмотрен алгоритм сортировки слиянием, он реализован в трех вариациях. Две актуальные реализации вынесены в специальные классы: TimSort, ComparableTimSort. TimSort предназначена для сортировки объектов с использованием компараторов. ComparableTimSort — это версия TimSort, предназначенная для сортировки объектов, поддерживающих Comparable. Подробности реализации сортировки TimSort смотрите в посте на хабре.

Класс TimSort содержит единственную пороговую величину, при сравнении с которой принимается решение о переключении на дополнительный алгоритм. Это величина называется MIN_MERGE и хранит минимальную длину массива, при которой будет производиться сортировка слиянием. Если же длина массива будет меньше MIN_MERGE, т.е. 32, то будет задействована бинарная сортировка вставками. Как сказано в документации, это мини-TimSort, т.е. без использования слияний.

Таблица 3. Дополнительные алгоритмы в TimSort.sort и ComparableTimSort.sort

Тип данных	Размер массива, n	Предпочитаемый алгоритм	Временная сложность в лучшем случае
T[]	n < 32	binary insertion sort	O(n)

Третья реализация сортировки слиянием является legacy и оставлена для сохранения обратной совместимости с версией JDK 1.6 и более ранними. Legacy сортировка обернута в метод legacyMergeSort и непосредственно реализована в методе Arrays.mergeSort. Для того, чтобы ее использовать, необходимо выставить флаг -Djava.util.Arrays.useLegacyMergeSort=true перед запуском виртуальной машины. Для хранения значения этой переменной в Arrays имеется внутренний статический класс LegacyMergeSort (см. Листинг. 1).

Листинг 1. Статический внутренний класс LegacyMergeSort в Arrays

При вызове Arrays.sort с массивом ссылочного типа происходит проверка, выставлен ли флаг на применение legacy сортировки. Тогда происходит вызов либо legacy сортировки, либо одной из базовых (см. Листинг 2).

Листинг 2. Реализация метода Arrays.sort для массива ссылочного типа с компаратором

Arrays.binarySearch

Для массивов как примитивных, так и ссылочных типов предусмотрен бинарный поиск. Перед поиском массив должен быть отсортирован. Сложность алгоритма бинарного поиска в среднем и в худшем случае составляет O(log n). Дополнительных алгоритмов не предусмотрено.

Collections.sort

В Collections сортировка предусмотрена только для списков. Интересно, что сначала производится преобразование списка в массив с последующим применением сортировки слиянием для массивов ссылочных типов. Сортировка осуществляется вызовом метода Arrays.sort.

Collections.binarySearch

Как и в случае с сортировкой, в Collections бинарный поиск реализован только для списков. Переменная BINARYSEARCH_THRESHOLD устанавливает ограничение на размер списка в 5000 элементов. Так что если вам необходимо провести поиск на более внушительной выборке, придется подумать, как это лучше сделать.

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

Всего интерфейс List в JDK 7.8 реализуют 10 классов, 2 из которых — абстрактные AbstractList и AbstractSequentialList. Последовательный доступ реализует только LinkedList и все потомки AbstractSequentialList. Поэтому они будут обрабатываться алгоритмом iteratorBinarySearch. Остальные списки, такие как ArrayList, CopyOnWriteArrayList, будут обрабатываться алгоритмом indexedBinarySearch.

UPD. Как стало понятно из личной дискуссии с Zamyslov, необходимо уточнить, каким образом BINARYSEARCH_THRESHOLD участвует в определении типа алгоритма сортировки. Это пороговое значение имеет влияние только на списки с последовательным доступом.

Cписок, поддерживающий произвольный доступ, будет всегда обрабатываться Collections.indexedBinarySearch. А список, поддерживающий последовательный доступ, будет обрабатываться Collections.iteratorBinarySearch только если он будет превышать значение BINARYSEARCH_THRESHOLD (см. листинг 3), в противном случае он также будет обрабатываться Collections.indexedBinarySearch.

Листинг 3. Влияние типов списков и константы BINARYSEARCH_THRESHOLD на определение алгоритмов обработки списка

Обобщаем изученное

Теперь, когда рассмотрены основные методы и условия перехода к дополнительным методам, можно обобщить полученные данные. Для максимальной наглядности детализируем рисунок 1, выделив на нем основные методы и добавим условия перехода к дополнительным методам.

Рисунок 2. Основные и дополнительные алгоритмы Arrays, Collections

Пояснения к цифрам на стрелках рисунка 2 содержатся в Сводной таблице. Цифры обозначают условия перехода. Серым выделены основные алгоритмы. Они применяются по умолчанию. В Сводной таблице строки, описывающие основные алгоритмы, выделены темно-серым.

*Сложности для основных алгоритмов приведены «в среднем случае», а сложности дополнительных алгоритмов приведены «в лучшем случае».

Collections sort java как работает

java.util.Collections.sort() method is present in java.util.Collections class. It is used to sort the elements present in the specified list of Collection in ascending order. It works similar to java.util.Arrays.sort() method but it is better than as it can sort the elements of Array as well as linked list, queue and many more present in it.

Sorting an ArrayList in ascending order

Time Complexity: O(N log N) as time complexity of Collections.sort() is O(nlog(n)).
Auxiliary Space: O(1)

Sorting an ArrayList in descending order

Time Complexity: O(N log N) as time complexity of Collections.sort() is O(nlog(n)).
Auxiliary Space: O(1)

Sorting an ArrayList according to user defined criteria. We can use Comparator Interface for this purpose.

Don’t write your own sort

If you are writing your own sorting algorithm in Java, unless you are doing so for the purpose of learning how to write a sorting algorithm (e.g. Insertion Sort, Quicksort, Mergesort, etc.), then you are probably doing something wrong.

To be honest, that’s true in most languages. For any given language and system, there is already, most likely, a built-in way of sorting things that need to be sorted. You just need to hook into that.

You write sorting algorithms in courses such as CMPSC 24 and CMPSC 130A so that you understand how sorting algorithms work, and how algorithms work in general But you should hardly ever write your own sort after that, ever again—certainly not if the purpose is to put things in order.

What you need to understand to do sorting in Java

To understanding sorting in Java, you need to understand these concepts:

• The interface java.lang.Comparable
• The interface java.util.Comparator

It is also super handy if you understand the concept called lambda Expressions, because it makes the code for using java.lang.Comparable and java.util.Comparator much cleaner, shorter, and more clear.

I’ll walk you through what you need to know.

ArrayList yes, but Vector and LinkedList too

All of my examples in this lesson use ArrayList since that’s the class that is most familiar to students from the classes that implement the java.util.List interface. However, everything we illustrate here works on java.util.Vector and java.util.LinkedList as well.

How to Sort an ArrayList<String>

Sorting an ArrayList<String> so that all of the strings appear in alphabetical order (or more correctly, lexicographic order) is super easy in Java.

It’s easy because String implements the java.util.Comparable<String> interface.

That is, it has a method: int compareTo(String o) that allows us to compare one String to another and determine whether:

• this string should come before o in lexicographic order, i.e. this string is “less than” o
• this string and o are equal
• this string should come after o in lexicographic, i.e. this string is “greater than” o

Anytime you have an ArrayList<T> where T is a type that implements Comparable , you can just use the method java.util.Collections.sort to sort the list. Here’s some sample code:

Running it, we get:

Sorting ArrayList<Dog> : First Attempt

What if we try the same thing with one of our own classes? Here’s a simple Dog class:

And here’s some code that tries to sort it:

But it doesn’t compile. We get this terrible looking error. What’s gone wrong?

The problem is that Dog doesn’t implement java.lang.Comparable<Dog> . Here’s a fixed version.

• We declare on line 1 that Dog implements Comparable<Dog> .
• We can leave off the java.lang. on java.lang.Comparable ; you can always leave off java.lang.
• Implementing Comparable<Dog> involves writing the compareTo method that appears on lines 15-29

Now our code compiles, and sorting works:

Sorting in more than one way

But, our Dog class has both name and weight . What if we want to sort by weight instead of by name?

The problem with sorting based on Comparable is that we can only define one way of sorting. We typically choose, when we implement Comparable , the most “obvious” way of sorting our class. The javadoc calls this the “natural order”, though to be honest, there is nothing “natural” about it; it’s just the way the programmer decides is the most “reasonable” way to be the default ordering for the class.

But, we typically want to sort in many different ways, and we may not even be able to anticipate all of them in advance. We don’t want to have to change the source code for the Dog class to be able to sort in new ways. That’s where java.util.Comparator<T> comes in.

A class that implements the Comparator<T> interface is one that implements the method:

That method looks a lot like the int compare(T o) method, except that it is not a method of class T ; instead, it’s an instance method of some other class. It may help to think of a Comparator<T> object as a kind of “plugin” or “add-on” that you use whenever you want to compare two objects of type T . As the meme goes, this class literally “has only one job”.

Here’s what a Comparator class for comparing Dog objects by weight would look like.

• The example above of DogWeightComparator.java is an example of writing a class that implements Comparator<Dog> as a separate standalone class, in it’s own file. In practice, that is almost never done.
• Instead, we typically make these little Comparator classes be inner classes, anonymous inner classes, or lambda expressions; but we’ll get to that. One thing at a time!

Ok, so with a DogWeightComparator class present, we can now write this code:

And when we run it, we get:

Using the sort method of ArrayList

Now that we have a class that implements Comparator<Dog> we could nalso use the built in sort method of java.util.ArrayList . That is instead of:

Note that if we import java.util.Collections then we can just write this for the first one:

An important thing to recognize is that if we invoke Collections.sort(kennel); without passing in a Compartor<Dog> object, we are using the “natural ordering”, i.e. the compareTo method of Dog , and that Dog must implement Comparable<Dog> in that case.

If we instead, use the sort method of ArrayList (e.g. kennel.sort(comparator) ) than we have to pass in a suitable object of a class that implements Comparator<Dog> .

At one level, that’s all you need to know. The rest, i.e. the stuff about Lambda Expressions, is all just stuff that makes writing the code easier. It may not seem that way on first read; it may seem awfully complicated. But once you really get it, it’s not complicated at all, and it makes your life so much easier if you spend a lot of time writing Java code. So, let’s dive in.

Easier sorting with Lambda Expressions

Lambda expressions give us a way to create a Comparator with much less bother.

• They are NOT more efficient in terms of memory, or run time or anything to do with computational efficiency
• But they are are more efficient for the human programmer.

They are a shorthand syntax. The best way to understand what they are is to consider four options for creating a comparator, each one moving us close to lambda expresions in stages.

Stage	Explanation	Example Code
Stage 1	Comparator as a separate standalone class, like we did with DogWeightComparator , and instantiate it with new DogWeightComparator() when we need a comparator object.	See DogWeightComparator above
Stage 2	Comparator as a named static inner class. The difference between this and Stage 1, is that we don’t need a separate .java source file.	See DogWeightInnerClass below
Stage 3	We create an instance of an anonymous inner class. This one is the most “mysterious”; it appears that we are doing something illegal, i.e. invoking a constructor on an interface, which we all “know” isn’t permitted, right? Except that we are actually, in that moment declaring a class (one with no name) and instantiating it, all at the same time. I know: that sounds confusing. It will make sense when we get there.	See DogWeightAnonymousInnerClass below
Stage 4	We realize that most of the syntax we wrote in Stage 3 is unnecessary; that is, the compiler can figure out most of what we wrote, so a shorter syntax makes things easier.	See DogWeightLambda below

Stage 2: Using a named inner class ( DogWeightInnerClass )

In the directory DogWeightInnerClass , we see that the file SortDogs3.java illustrates how we can move the compartor inside the class where we declare our main program, like this:

But we can do better than this.

Stage 3: Anonymous Inner Class Instance ( DogWeightAnonymousInnerClass )

In this example, we are almost at the stage of introducing Lambda Expressions; indeed, prior to Java 8, the syntax I’m about to show you was considered the “best” way of making Comparator objects.

If we are only going to use our inner class once, rather than give it a name, and declare it far away from where it is used, we can declare it like this:

Here’s that code in context. Note that we are importing java.util.Comparator on line 2 so that we don’t have to specify the full package name each time we refer to a Comparator . Also note how we use the sortByWeight object of type Comparator<Dog> on line xx as the parameter to kennel.sort(sortByWeight)

Stage 4: Using Lambdas ( DogWeightLambda )

Here, finally, we see that we can make the declaration of the anonymous inner class much shorter.

We can write the single line of code:

Here’s how to interpret this:

New Syntax	Replaces	Explanation
(o1, o2)	(Dog o1, Dog o2)	We need to give names to the variables that are parameters to the compare method. But the types are implied. Since it’s a Comparator<Dog> , it is understood that the method we are defining is compare , and the types of the two parameters are both Dog .
->	return	The -> indicates that what follows is the expression that will come after the return
Double.compare(o1.getWeight(),o2.getWeight())	(same)	We need to specify what the compare method returns, in terms of o1 and o2

It’s as simple as that. To make a comparator, we just specify an expression of this form, where T is some type:

Comparator<T> myComparator = (o1, o2) -> expression ;

If computing the return value is more complicated, we can also put a full block of code in braces after the -> . Here’s an example of what that would look like:

Another Example, for Review: StudentSort01.java

To review everything, consider this program, which uses all of the techniques we’ve discussed:

Understanding Collections.sort() in Java

As the name suggests, the Collections class of java provides a static method called sort() which is used to sort a collection of items in a particular order.

Let’s look at the definition of this method. As we can see, it takes two arguments, one is the List of objects of type T and other is a Comparator which accepts objects of type T and return an order in which list sorting has to be done. In this function definition, we are giving a Comparator to define a sorting order explicitly.

There is one more definition for Collections.sort() method.

In this definition, static sort method only accepts the List of objects of type T and it sorts them in a default order. Here we can see that, to sort T in some default order, T must implement the Comparable interface.

It is important to note that,

All wrapper classes and String class implement Comparable interface in Java. Wrapper classes are compared by their values, and strings are compared lexicographically. By default, they sort the elements in the ascending order.

To sort the remaining objects of type, T, using Collections.sort() method, either:

1. The object should implement the Comparable interface, or,
2. We should define a custom Comparator that can sort the objects of type T and pass it into our sort function as the second argument.

Comparable interface

Taking an example of Integer wrapper class. Integer class implements Comparable interface. Comparable interface has a method called as compareTo(). Inside the Integer class, it overrides the compareTo method. It compares the current object with the object being passed in the sort function, let’s call it var1 and it returns -1,0,1 when the current object is less than var1, when current object equals to var1 and when current object is greater than var1, respectively.

So, it means whenever a class implements the Comparable interface, it can add it’s own logic in compareTo function and hence can have it’s own logic for sorting.

Now, what if we want to sort the objects of type T in some other order that is different from the default ordering. To solve this, Comparator comes into picture.

Comparator interface

When we want to define an ordering for sorting the objects of some type T, we can create a custom Comparator, which we can pass in our Collections.sort() method as the second argument while sorting List<T> list.

Comparator is a functional interface.
A functional interface in Java is an interface that contains only a single abstract (unimplemented) method. A functional interface can contain default and static methods which do have an implementation, in addition to the single unimplemented method.

Comparator interface has a single abstract method known as compare(). It compares the two objects T1 and T2 and generally returns -1, 0, 1 when T1<T2, when T1==T2 and when T1>T2, respectively in most of the implementations.

Example illustrating the use of Comparator interface while sorting the objects of type T in ascending order.

Suppose Object T has following two attributes: dataLimit, dataUsed both of type integer.

Defining the Comparator inside the function argument

Defining the Comparator outside and passing it’s object in function’s argument

Using lambda expression with Constructor

To sort in descending order: This function reversed() can used with any Comparator by function chaining to change the sorting logic to reverse order.

You can explore more methods of comparable and Comparator interface and understand it’s working by digging deep into the wrapper classes.

Guys I really hope that you find this article valuable! If still you have any queries, you can surely discuss them in the comment section below.

Thanks a lot for devoting your time to this blog.

Please share it among your colleagues and clap for showing appreciation! 🙂