정렬

정렬

알고리즘 문제를 풀다보면, 혹은 개발을 하다보면 배열을 정렬해야 할 때가 있다.

이 때 우리는 Arrays.sort() 를 이용해 배열을 정렬한다.

단일 배열의 정렬

int 배열을 기준으로 단일 배열의 정렬을 알아보자.

오름차순

int[] arr = {2, 1, 5, 7, 91, 10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));

// [1, 2, 5, 7, 10, 91]

내림차순

Integer[] arr = {2, 1, 5, 7, 91, 10};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(Arrays.toString(arr));

// [91, 10, 7, 5, 2, 1]

여기서 sort()에 두번째로 들어가는 Collections.reverseOrder()은 무엇일까?

이는 사실 Comparator 인터페이스의 구현 객체이다.

인터페이스인 Comparator은 직접 구현해야 하지만, 내림차순은 자주 사용되기 때문에 Collections에서 기본적으로 제공하는 것이다.

그렇다면 이해를 위해 Comparator인터페이스를 직접 구현해 내림차순을 만들어보자.

Integer[] arr = {2, 1, 5, 7, 91, 10};

Arrays.sort(arr, new Comparator<Integer>(){
    @Override
    public int compare(Integer o1, Integer o2){
        return o2 - o1;
    }
});

// 람다식을 사용해 더 간결한 구현 가능
Arrays.sort(arr, (o1, o2) -> o2-o1);

//결과 [91, 10, 7, 5, 2, 1]

이차원 배열의 정렬

그렇다면 2차원 배열을 정렬하려 하면 어떻게 해야할까?

예를 들어 길이가 2인 int 배열을 원소로 갖는 이차원 배열을 생각해보자.

[ [0, 3], [1, 4], [2, 4], [3, 5] ] 같은 배열이 있다. 각 원소의 두 번째 값을 기준으로 정렬하고, 만약 같으면 첫 번째 값을 기준으로 정렬하려고 한다.

int[][] arr = {{0,3}, {3,5}, {2,4}, {1,4}};

Arrays.sort(arr, new Comparator<int[]>(){
    @Override
    public int compare(int[] o1, int[] o2){
        if(o1[1] == o2[1]){
            return o1[0] - o2[0];
        }
        return o1[1] - o2[1];
    }
});

// 람다식 사용
Arrays.sort(arr, (o1, o2) -> {
    if(o1[1] == o2[1]){
        return o1[0] - o2[0];
    }
    return o1[1] - o2[1];
});

// 결과 [ [0, 3], [1, 4], [2, 4], [3, 5] ]

위처럼 적절하게 Comparator 인터페이스의 compare() 추상메서드를 구현하면, 필요한 기준에 따라 정렬할 수 있다.