Java에서 정렬

1. 개요

이 기사에서는 Java 7 및 Java 8에서 Array , List , SetMap 에 정렬을 적용하는 방법을 설명합니다 .

2. 배열로 정렬

먼저 Arrays.sort () 메서드를 사용하여 정수 배열을 정렬하는 것으로 시작하겠습니다 .

@Before jUnit 메서드 에서 다음과 같은 int 배열을 정의합니다 .

@Before public void initVariables () { toSort = new int[] { 5, 1, 89, 255, 7, 88, 200, 123, 66 }; sortedInts = new int[] {1, 5, 7, 66, 88, 89, 123, 200, 255}; sortedRangeInts = new int[] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ... }

2.1. 전체 배열 정렬

이제 간단한 Array.sort () API를 사용하겠습니다 .

@Test public void givenIntArray_whenUsingSort_thenSortedArray() { Arrays.sort(toSort); assertTrue(Arrays.equals(toSort, sortedInts)); }

정렬되지 않은 배열은 이제 완전히 정렬됩니다.

[1, 5, 7, 66, 88, 89, 123, 200, 255]

공식 JavaDoc에서 언급했듯이 Arrays.sort기본 요소 에서 이중 피벗 Quicksort를 사용합니다 . O (n log (n)) 성능을 제공하며 일반적으로 기존 (one-pivot) Quicksort 구현보다 빠릅니다. 그러나 객체 배열 에 대한 병합 정렬 알고리즘의 안정적이고 적응 적이며 반복적 인 구현을 사용합니다 .

2.2. 배열의 일부 정렬

Arrays.sort 에는 정렬 API 가 하나 더 있습니다. 여기에서 설명하겠습니다.

Arrays.sort(int[] a, int fromIndex, int toIndex)

이것은 두 인덱스 사이에서 배열의 일부만 정렬합니다.

간단한 예를 살펴 보겠습니다.

@Test public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray() { Arrays.sort(toSort, 3, 7); assertTrue(Arrays.equals(toSort, sortedRangeInts)); }

정렬은 다음 하위 배열 요소에서만 수행됩니다 ( toIndex 는 배타적 임).

[255, 7, 88, 200]

기본 배열을 포함한 결과 정렬 된 하위 배열은 다음과 같습니다.

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3. Java 8 Arrays.sortArrays.parallelSort

Java 8에는 Arrays.sort () API 와 유사한 서명 이있는 새로운 API 인 parallelSort 가 제공됩니다 .

@Test public void givenIntArray_whenUsingParallelSort_thenArraySorted() { Arrays.parallelSort(toSort); assertTrue(Arrays.equals(toSort, sortedInts)); }

의 배후 parallelSort () 는 (의 알고리즘과 같은 다른 단위마다의 서브 어레이로 배열 나누기 parallelSort ). 각 하위 배열은 서로 다른 스레드에서 Arrays.sort ()정렬 되어 정렬 이 병렬 방식으로 실행될 수 있고 마지막으로 정렬 된 배열로 병합됩니다.

ForJoin 공통 풀은 이러한 병렬 작업을 실행 한 다음 결과를 병합하는 데 사용됩니다.

Arrays.parallelSort 의 결과는 물론 Array.sort 와 동일 할 것 입니다. 멀티 스레딩을 활용하는 문제 일뿐입니다.

마지막으로, 유사한 API의 변종이있다 Arrays.sort에Arrays.parallelSort 뿐만 아니라이 :

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

3. 목록 정렬

이제 java.utils.Collections 에서 Collections.sort () API를 사용하여 정수 목록 을 정렬 해 보겠습니다 .

@Test public void givenList_whenUsingSort_thenSortedList() { List toSortList = Ints.asList(toSort); Collections.sort(toSortList); assertTrue(Arrays.equals(toSortList.toArray(), ArrayUtils.toObject(sortedInts))); }

목록 다음과 같은 요소가 포함됩니다 정렬하기 전에 :

[5, 1, 89, 255, 7, 88, 200, 123, 66]

그리고 자연스럽게 정렬 후 :

[1, 5, 7, 66, 88, 89, 123, 200, 255]

Collections.Sort 용 Oracle JavaDoc에서 언급했듯이 수정 된 병합 정렬을 사용하고 보장 된 n log (n) 성능을 제공합니다.

4. 세트 정렬

다음으로, LinkedHashSet 을 정렬하기 위해 Collections.sort () 를 사용합시다 .

삽입 순서를 유지하기 때문에 LinkedHashSet을 사용하고 있습니다.

공지 방법, 사용하기 위해 정렬 에서 API 컬렉션 - 우린 처음 포장을 세트 목록에서 :

@Test public void givenSet_whenUsingSort_thenSortedSet() { Set integersSet = new LinkedHashSet(Ints.asList(toSort)); Set descSortedIntegersSet = new LinkedHashSet( Arrays.asList(new Integer[] {255, 200, 123, 89, 88, 66, 7, 5, 1})); List list = new ArrayList(integersSet); Collections.sort(Comparator.reverseOrder()); integersSet = new LinkedHashSet(list); assertTrue(Arrays.equals( integersSet.toArray(), descSortedIntegersSet.toArray())); }

Comparator.reverseOrder () 메소드는 자연 순서에 의해 부과 된 순서를 반전시킵니다.

5. 지도 정렬

이 섹션에서는 키와 값으로 맵정렬하는 방법을 살펴 보겠습니다 .

먼저 정렬 할 맵을 정의하겠습니다.

@Before public void initVariables () { .... HashMap map = new HashMap(); map.put(55, "John"); map.put(22, "Apple"); map.put(66, "Earl"); map.put(77, "Pearl"); map.put(12, "George"); map.put(6, "Rocky"); .... }

5.1. 키로 정렬

We'll now extract keys and values entries from the HashMap and sort it based on the values of the keys in this example:

@Test public void givenMap_whenSortingByKeys_thenSortedMap() { Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 }; List
    
      entries = new ArrayList(map.entrySet()); Collections.sort(entries, new Comparator
     
      () { @Override public int compare( Entry o1, Entry o2) { return o1.getKey().compareTo(o2.getKey()); } }); Map sortedMap = new LinkedHashMap(); for (Map.Entry entry : entries) { sortedMap.put(entry.getKey(), entry.getValue()); } assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys)); }
     
    

Note how we used the LinkedHashMap while copying the sorted Entries based on keys (because HashSet doesn't guarantee the order of keys).

The Map before sorting :

[Key: 66 , Value: Earl] [Key: 22 , Value: Apple] [Key: 6 , Value: Rocky] [Key: 55 , Value: John] [Key: 12 , Value: George] [Key: 77 , Value: Pearl]

The Map after sorting by keys:

[Key: 6 , Value: Rocky] [Key: 12 , Value: George] [Key: 22 , Value: Apple] [Key: 55 , Value: John] [Key: 66 , Value: Earl] [Key: 77 , Value: Pearl] 

5.2. Sorting Map by Values

Here we will be comparing values of HashMap entries for sorting based on values of HashMap:

@Test public void givenMap_whenSortingByValues_thenSortedMap() { String[] sortedValues = new String[] { "Apple", "Earl", "George", "John", "Pearl", "Rocky" }; List
    
      entries = new ArrayList(map.entrySet()); Collections.sort(entries, new Comparator
     
      () { @Override public int compare( Entry o1, Entry o2) { return o1.getValue().compareTo(o2.getValue()); } }); Map sortedMap = new LinkedHashMap(); for (Map.Entry entry : entries) { sortedMap.put(entry.getKey(), entry.getValue()); } assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues)); }
     
    

The Map before sorting:

[Key: 66 , Value: Earl] [Key: 22 , Value: Apple] [Key: 6 , Value: Rocky] [Key: 55 , Value: John] [Key: 12 , Value: George] [Key: 77 , Value: Pearl]

The Map after sorting by values:

[Key: 22 , Value: Apple] [Key: 66 , Value: Earl] [Key: 12 , Value: George] [Key: 55 , Value: John] [Key: 77 , Value: Pearl] [Key: 6 , Value: Rocky]

6. Sorting Custom Objects

Let's now work with a custom object:

public class Employee implements Comparable { private String name; private int age; private double salary; public Employee(String name, int age, double salary) { ... } // standard getters, setters and toString }

We'll be using the following Employee Array for sorting example in the following sections:

@Before public void initVariables () { .... employees = new Employee[] { new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)}; employeesSorted = new Employee[] { new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000), new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)}; employeesSortedByAge = new Employee[] { new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)}; }

We can sort arrays or collections of custom objects either:

  1. in the natural order (Using the Comparable Interface) or
  2. in the order provided by a ComparatorInterface

6.1. Using Comparable

The natural order in java means an order in which primitive or Object should be orderly sorted in a given array or collection.

Both java.util.Arrays and java.util.Collections have a sort() method, and It's highly recommended that natural orders should be consistent with the semantics of equals.

In this example, we will consider employees with the same name as equal:

@Test public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() { Arrays.sort(employees); assertTrue(Arrays.equals(employees, employeesSorted)); }

You can define the natural order for elements by implementing a Comparable interface which has compareTo() method for comparing current object and object passed as an argument.

To understand this clearly, let's see an example Employee class which implements Comparable Interface:

public class Employee implements Comparable { ... @Override public boolean equals(Object obj) { return ((Employee) obj).getName().equals(getName()); } @Override public int compareTo(Object o) { Employee e = (Employee) o; return getName().compareTo(e.getName()); } }

Generally, the logic for comparison will be written the method compareTo. Here we are comparing the employee order or name of the employee field. Two employees will be equal if they have the same name.

Now when Arrays.sort(employees); is called in the above code, we now know what is the logic and order which goes in sorting the employees as per the age :

[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000), ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]

We can see the array is sorted by name of the employee – which now becomes a natural order for Employee Class.

6.2. Using Comparator

Now, let's sort the elements using a Comparator interface implementation – where we pass the anonymous inner class on-the-fly to the Arrays.sort() API:

@Test public void givenIntegerArray_whenUsingSort_thenSortedArray() { Integer [] integers = ArrayUtils.toObject(toSort); Arrays.sort(integers, new Comparator() { @Override public int compare(Integer a, Integer b) { return Integer.compare(a, b); } }); assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts))); }

Now lets sort employees based on salary – and pass in another comparator implementation:

Arrays.sort(employees, new Comparator() { @Override public int compare(Employee o1, Employee o2) { return Double.compare(o1.getSalary(), o2.getSalary()); } });

The sorted Employees arrays based on salary will be:

[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Earl,43,10000.0)] 

Note that we can use Collections.sort() in a similar fashion to sort List and Set of Objects in Natural or Custom order as described above for Arrays.

7. Sorting With Lambdas

Start with Java 8, we can use Lambdas to implement the Comparator Functional Interface.

You can have a look at the Lambdas in Java 8 writeup to brush up on the syntax.

Let's replace the old comparator:

Comparator c = new Comparator() { @Override public int compare(Integer a, Integer b) { return Integer.compare(a, b); } }

With the equivalent implementation, using Lambda expression:

Comparator c = (a, b) -> Integer.compare(a, b);

Finally, let's write the test:

@Test public void givenArray_whenUsingSortWithLambdas_thenSortedArray() { Integer [] integersToSort = ArrayUtils.toObject(toSort); Arrays.sort(integersToSort, (a, b) -> { return Integer.compare(a, b); }); assertTrue(Arrays.equals(integersToSort, ArrayUtils.toObject(sortedInts))); }

As you can see, a much cleaner and more concise logic here.

8. Using Comparator.comparing and Comparator.thenComparing

Java 8 comes with two new APIs useful for sorting – comparing() and thenComparing() in the Comparator interface.

These are quite handy for the chaining of multiple conditions of the Comparator.

Let's consider a scenario where we may want to compare Employee by age and then by name:

@Test public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() { List employeesList = Arrays.asList(employees); employees.sort(Comparator.comparing(Employee::getAge)); assertTrue(Arrays.toString(employees.toArray()) .equals(sortedArrayString)); }

In this example, Employee::getAge is the sorting key for Comparator interface implementing a functional interface with compare function.

Here's the array of Employees after sorting:

[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Pearl,33,6000.0), (Earl,43,10000.0)]

Here the employees are sorted based on age.

We can see John and Jessica are of same age – which means that the order logic should now take their names into account- which we can achieve with thenComparing():

... employees.sort(Comparator.comparing(Employee::getAge) .thenComparing(Employee::getName)); ... 

After sorting with above code snippet, the elements in employee array would be sorted as:

[(Jessica,23,4000.0), (John,23,5000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Pearl,33,6000.0), (Earl,43,10000.0) ]

Thus comparing() and thenComparing() definitely make more complex sorting scenarios a lot cleaner to implement.

9. Conclusion

In this article, we saw how we can apply sorting to Array, List, Set, and Map.

우리는 또한 자바 8의 기능, 람다의 사용과 같은 분류에 유용 할 수있는 방법에 대한 간단한 소개했다 비교 ()thenComparing ()parallelSort () .

이 기사에 사용 된 모든 예제는 GitHub에서 사용할 수 있습니다.