[Java] Arrays.sort(), compareTo에 대해서 알아보기

정리를 하게된 계기

프로그래머스에서 알고리즘 문제를 풀던 도중 이해하기 어려운 코드 한줄을 발견했다.
Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

다익스트라 알고리즘을 공부하면서 PriorityQueue를 사용할 때 compareTo를 Override해서 사용한 적이 있는데 명확하게 이해하지 못한 것 같아 짚고 넘어가려 한다.

Arrays.sort()란?

공식 문서를 보면 여러 타입의 배열이 모두 정렬될 수 있도록 정의된 것을 볼 수 있다.

동작과정을 살펴보면 다음과 같다.

// Arrays class
public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
}

...
// DualPivotQuicksort class

static void sort(int[] a, int parallelism, int low, int high) {
    int size = high - low;
    if (parallelism > 1 && size > 4096) {
       int depth = getDepth(parallelism, size >> 12);
       int[] b = depth == 0 ? null : new int[size];
       (new Sorter((CountedCompleter)null, a, b, low, size, low, depth)).invoke();
    } else {
        sort((Sorter)null, (int[])a, 0, low, high);
    }
}

static void sort(Sorter sorter, int[] a, int bits, int low, int high) {
        while(true) {
            int end = high - 1;
            int size = high - low;
            if (size < 65 + bits && (bits & 1) > 0) {
                mixedInsertionSort(a, low, high - 3 * (size >> 5 << 3), high);
                return;
            }

            if (size < 44) {
                insertionSort(a, low, high);
                return;
            }
            
...(생략)

내부적으로 두개의 pivot을 사용하는 Quicksort로 동작하며 시간 복잡도는 O(n log n)으로 좋은 성능을 가지기 때문에 알고리즘을 풀때 사용해도 큰 문제가 없을 것 같다.

매개 변수에는 3가지 정도가 있다.

• fromIndex(시작 인덱스)
• toIndex(마지막 인덱스)
• Comparator<? super T> c

Interface Comparator< T >

주목해야할 매개변수로 인터페이스인 Comparator은 람다 표현식 등을 사용한 비교기를 정렬 방법으로 전달할 수 있다고 명시되어있다.

---

Example

기본 형태(오름차순)

public static void main(String[] args) {
	String[] words = {"banana", "apple", "orange", "kiwi"};

	Arrays.sort(words);

	System.out.println("문자열 정렬: " + Arrays.toString(words));

	Integer[] numbers = {5, 1, 8, 3, 7};

	Arrays.sort(numbers);

	System.out.println("숫자 정렬: " + Arrays.toString(numbers));
}

// 실행 결과
문자열 정렬: [apple, banana, kiwi, orange]
숫자 정렬: [1, 3, 5, 7, 8]

기본적인 형태로 default는 오름차순으로 정렬한다. sort함수에 정렬할 배열만 넣어 사용할 수 있다. 문자열을 정렬할 때는 알파벳 순서(ASCII code 비교)로 정렬하게 되고 같은 알파벳일 경우 그 다음 문자열을 비교해서 정렬하게 된다.

String[] words = {"aanana", "apple", "orange", "kiwi"};

Arrays.sort(words);

System.out.println("문자열 정렬: " + Arrays.toString(words));

//실행 결과
문자열 정렬: [aanana, apple, kiwi, orange]

내림차순 정렬(Comparator)

public static void main(String[] args) {
	String[] words = {"banana", "apple", "orange", "kiwi"};

	Arrays.sort(words, Comparator.reverseOrder());

	System.out.println("문자열 정렬(내림차순): " + Arrays.toString(words));

	Integer[] numbers = {5, 1, 8, 3, 7};

	Arrays.sort(numbers, Comparator.reverseOrder());

	System.out.println("숫자 정렬(내림차순): " + Arrays.toString(numbers));
}

// 실행 결과
문자열 정렬(내림차순): [orange, kiwi, banana, apple]
숫자 정렬(내림차순): [8, 7, 5, 3, 1]

Comparator.reverseOrder()을 추가해서 내림차순으로 정렬할 수 있다.

public static void main(String[] args) {
	Integer[] numbers = {5, 1, 8, 3, 7};

	Arrays.sort(numbers, (a, b) -> b - a);

	System.out.println("내림차순 정렬: " + Arrays.toString(numbers));
}

람다 표현식으로 a,b를 비교하여 내림차순으로 정렬하는 방법이다.

• b - a가 양수면, b가 a보다 크기 때문에 b가 앞에 와야한다.
• b - a가 음수면, a가 b보다 크기 때문에 a가 그대로 유지된다.

Comparator 응용

이전 내림차순 정렬을 위해 사용한 람다식 표현으로 더 복잡한 정렬기준을 만들어서 정렬을 할 수 있다.

• 2차원 배열에서 첫번째 요소로만 정렬하고 싶을 때
• 이전 값과의 연산을 통해 정렬 기준을 정할 때

상황에 더 따라 다양하게 사용할 수 있는데 실제로 필요했던 예시만 언급했다.

1. 2차원 배열의 정렬 조건

public static void main(String[] args) {
    Integer[][] workers = {{1, 280}, {3, 120}, {2, 150}, {5, 400}, {4, 330}};

    Arrays.sort(workers, (a, b) -> b[1].compareTo(a[1]));

    System.out.println("급여(내림차순) 정렬: " + Arrays.deepToString(workers));

// 실행결과
급여(내림차순) 정렬: [[5, 400], [4, 330], [1, 280], [2, 150], [3, 120]]
}

ID, 급여 정보가 있는 2차원 배열이 있다고 생각해보자. 만약 급여가 높은 순서대로 정렬하고 싶다면 다음과 같이 코드를 작성할 수 있다.

(a, b) -> b[1].compareTo(a[1]) 는 람다 표현식으로, 정렬 기준이 된다.

• a, b배열의 두개의 요소

  • example
  • a는 {1 , 280} , b는 {3 , 120}

• b[1], a[1]로 배열의 두번째(급여)를 사용하여 비교

• 동작과정

  • b[1]가 a[1]보다 크면 양수가 반환되어 b가 a앞에 위치한다.
  • b[1]가 a[1]보다 작으면 음수가 반환되어 순서가 유지된다.
  • b[1]가 a[1]보다 같으면 순서를 바꾸지 않는다.

---

2. 이전 값과의 연산을 통한 정렬기준

프로그래머스 가장 큰 수 를 풀 때 필요한 솔루션으로 문제 상황은 다음과 같다.

public class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));
        
      	...
    }
}

주어진 입력 값을 String 배열로 변환 후에 Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2)); 로 정렬을 수행했다.

동작 과정
a = 30 , b = 34 라고 할 때, "3430"이 "3034"보다 크기 때문에 양수가 반환되어 b가 a보다 앞에 위치하게 된다. 이런식으로 내림차순으로 정렬해서 가장 큰 수의 문자열을 만들 수 있다.