Сортировка массива в Java
В этой статье будут обсуждаться различные методы сортировки массива примитивных типов или объектов в Java.
1. Сортировка массива с помощью Arrays.sort() метод
Arrays class предоставляет несколько статических методов для сортировки массивов:
Он сортирует указанный массив типов примитивов или объектов в порядке возрастания в соответствии с естественным порядком его элементов.
У него также есть версия, которая сортирует указанный массив между указанным диапазоном:
Arrays.sort() использует Dual-Pivot Quicksort, который предлагает O(n.log(n)) производительность. Обычно это быстрее, чем традиционный (одноповоротный) Быстрая сортировка реализации.
⮚ sort(T[] a, Comparator c)
Он сортирует указанный массив объектов в соответствии с порядком, заданным указанным компаратором. Он требует, чтобы все элементы массива были взаимно сравнимы указанным компаратором, т. е. для любой пары элементов (e1, e2) в массиве, c.compare(e1, e2) не следует бросать ClassCastException .
⮚ Чтобы отсортировать по возрастанию:
⮚ Чтобы отсортировать по убыванию:
Мы также можем написать собственный компаратор, как показано ниже:
Он также предоставляет версию, которая сортирует указанный массив объектов между указанным диапазоном в соответствии с порядком, заданным указанным компаратором:
Java Sort Array – How to Reverse an Array in Ascending or Descending Order with Arrays.sort()
Ihechikara Vincent Abba
In Java, you use arrays to store a collection of variables (with the same data type) in a single variable.
In many cases, the values stored in an array appear in a random order. Using the Arrays class in Java, you have access to various methods you can use to manipulate arrays.
One of the methods we’ll be using from the Arrays class is the sort() method which sorts an array in ascending order.
We’ll also see how to sort an array in descending order using the reverseOrder() method from the Collections class in Java.
How to Sort an Array in Ascending Order in Java Using Arrays.sort()
In this section, we’ll see an example on how we can use the sort() method to sort an array in ascending order.
The first thing we did in the example above was to import the Arrays class: import java.util.Arrays; . This give us access to all the methods of the Arrays class.
We then created an array with numbers in a random order: int[] arr = < 5, 2, 1, 8, 10 >; .
In order to sort this array in ascending order, we passed in the array as parameter to the sort() method: Arrays.sort(arr); .
Note that the Arrays class was written first before accessing the sort() method using dot notation.
Lastly, we looped through and printed the array in the console. The result was a sorted array: 1, 2, 5, 8, 10 .
In the next section, we’ll talk about sorting an array in descending order.
How to Sort an Array in Descending Order in Java Using Collections.reverseOrder()
To sort an array in descending order, we use the reverseOrder() which we can access from the Collections class.
We’ll still make use of Arrays.sort(); , but in this example, it’ll take in two parameters – the array to be sorted and Collections.reverseOrder() .
Here’s an example:
First things first, we imported the Arrays and Collections classes because we’ll be making use the methods provided by the classes.
We then created an array of numbers in random order: Integer[] arr = < 5, 2, 1, 8, 10 >; . You’ll notice that we used Integer[] instead of int[] like we did in the last example – the latter would throw an error.
To sort the array in descending order, we did this: Arrays.sort(arr, Collections.reverseOrder()); .
The first parameter is the array arr which will be sorted in ascending order. The second parameter – Collections.reverseOrder() – will then reverse the order of the sorted array so it is arranged in descending order.
When looped through and printed, the array would look like this: 10, 8, 5, 2, 1 .
Summary
In this article, we talked about sorting arrays in Java. Arrays can be sorted in ascending or descending order.
We can sort arrays in ascending order using the sort() method which can be accessed from the Arrays class. The sort() method takes in the array to be sorted as a parameter.
To sort an array in descending order, we used the reverseOrder() method provided by the Collections class. This is passed in as a second parameter in the sort() method so that the sorted array can be rearranged in descending order.
Arrays, Collections: Алгоритмический минимум
Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники Oracle JDK 7.80 (UPD: добавлена ссылка).
В самом обобщенном виде результат изучения представлен на рисунке. Подробности — в основном тексте.
Рисунок 1. Методы Arrays, Collections и реализуемые ими алгоритмы
Первое, что поразило меня в алгоритмах, реализованных в Arrays и Collections — то, что их можно буквально по пальцам пересчитать — по большому счету, это два алгоритма сортировки и один алгоритм поиска.
Второе — то, что сортировка списков «под капотом» использует сортировку массивов.
Третье — то, что один из алгоритмов сортировки портирован с python.
Алгоритм быстрой сортировки с двумя опорными элементами разработан нашим соотечественником Владимиром Ярославским и реализован при содействии Джона Бентли и Джошуа Блоха.
Алгоритм сортировки слиянием, который является основным для сортировки массивов ссылочных типов, буквально назван по имени своего создателя Tim Peters — TimSort. Этот алгоритм был адаптирован Джошуа Блохом с алгоритма сортировки списков, реализованном на python Тимом Петерсом.
Кратко излагая результаты, стоит отметить, что:
- Можно условно выделить три слоя методов:
- Методы API
- Методы базовых (основных) алгоритмов
- Методы (блоки) дополнительных алгоритмов
- Основных алгоритмов используется три. Два алгоритма сортировки: быстрая сортировка, сортировка слиянием. Один алгоритм поиска: бинарный поиск.
- Для оптимизации «основные» алгоритмы заменяются на более подходящие в данный момент “дополнительные” алгоритмы (полный список алгоритмов и условий переключения приведен в конце)
- Для определения того, какой из «дополнительных» алгоритмов будет задействован, могут использоваться:
- сигнатуры методов (типы аргументов, булевы переменные)
- флаги 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 содержатся в Сводной таблице. Цифры обозначают условия перехода. Серым выделены основные алгоритмы. Они применяются по умолчанию. В Сводной таблице строки, описывающие основные алгоритмы, выделены темно-серым.
*Сложности для основных алгоритмов приведены «в среднем случае», а сложности дополнительных алгоритмов приведены «в лучшем случае».
Sort an array in Java
I’m trying to make a program that consists of an array of 10 integers which all has a random value, so far so good.
However, now I need to sort them in order from lowest to highest value and then print it onto the screen, how would I go about doing so?
(Sorry for having so much code for a program that small, I ain’t that good with loops, just started working with Java)
19 Answers 19
Loops are also very useful to learn about, esp When using arrays,
Add the Line before println and your array gets sorted
It may help you understand loops by implementing yourself. See Bubble sort is easy to understand:
Of course, you should not use it in production as there are better performing algorithms for large lists such as QuickSort or MergeSort which are implemented by Arrays.sort(array)
I was lazy and added the loops
Your array has a length of 10. You need one variable ( i ) which takes the values from 0 to 9 .
Is a library methods that sorts arrays.
will do the job perfectly
For natural order : Arrays.sort(array)
For reverse Order : Arrays.sort(array, Collections.reverseOrder()); — > It is a static method in Collections class which will further call an inner class of itself to return a reverse Comparator.
You can sort a int array with Arrays.sort( array ) .
See below, it will give you sorted ascending and descending both
Note: You can use Math.ranodm instead of adding manual numbers. Let me know if I need to change the code.
Good Luck. Cheers.
Here is how to use this in your program:
just FYI, you can now use Java 8 new API for sorting any type of array using parallelSort
parallelSort uses Fork/Join framework introduced in Java 7 to assign the sorting tasks to multiple threads available in the thread pool.
the two methods that can be used to sort int array,
Java 8 provides the option of using streams which can be used to sort int[] array as:
As mentioned in doc for parallelSort :
The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method. If the length of the specified array is less than the minimum granularity, then it is sorted using the appropriate Arrays.sort method. The algorithm requires a working space no greater than the size of the original array. The ForkJoin common pool is used to execute any parallel tasks.
So if the input array is less than granularity (8192 elements in Java 9 and 4096 in Java 8 I believe), then parallelSort simply calls sequential sort algorithm.
Just in case we want to reverse sort the integer array we can make use of comparator as:
Since Java has no way to sort primitives with custom comparator, we have to use intermediate boxing or some other third party library which implements such primitive sorting.