자바로 알고리즘 시작하기 4 - 사용자 정의 객체 정렬

순서를 갖지 않는 HashSet과 같은 자료구조를 제외하고, List 계열이나 SortedSet, SortedMap 자식 객체들은 정렬이 가능하다. 또한 custom class를 정의한 것 또한 필요한 조치만 해 주면 정렬이 가능하다. 이를 어떻게 하는지 알아보자.

컬렉션을 정렬하는 인터페이스: Comparator와 Comparable

우리가 int 배열이나 Integer, Double과 같은 numeric 데이터에 대하여는 쉽게 정렬을 해왔다. 심지어 String도 내부적으로 정렬을 위한 구현 코드가 정의되어 있어 별도로 조치하지 않아도 정렬을 해 줬다.

하지만 우리는 종종 (x,y) 형태의 좌표를 custom class로 정의하거나, 유관 데이터를 별도 객체로 묶어서 정의한 뒤에 정렬을 해야 하는 상황과 마주치게 되는데, 이럴 때마다 자바가 어색한 사람들은 객체 정렬을 할 수 없다는 에러를 손쉽게 만나게 된다.

컴퓨터는 정렬을 하는 과정에서 대소 비교를 수행해야 한다. 즉, 데이터 간 순서를 숫자로 표현해야 한다는 것이다. 따라서 numeric 데이터에 대하여는 별도 조치 없이 정렬을 해왔는데, 복잡한 객체 정렬의 경우에는 난항을 겪는 것이다. 근데, custom class에서 Comparator 또는 Comparable을 implement하면 객체 정렬을 사용할 수 있다.

Comparable

Comparable 인터페이스는 Collection.sort() 메서드를 이용하여 정렬할 수 있도록 만들어준다. 기본적으로 사용자 정의 객체를 담은 컬렉션을 정렬할 때에는 이처럼 Comparable을 구현해야 한다고 이해하면 된다.

Comparable 인터페이스에는 compareTo() 메서드가 정의되어 있고, Collection.sort() 메서드는 컬렉션에 있는 element 객체의 compareTo() 메서드를 호출하여 비교값을 바탕으로 정렬을 하도록 구현되어 있다. 따라서 이를 구현해주면 정렬이 가능하다.

거두절미하고 코드를 보자.

private static class Pair implements Comparable<Pair> {  
    private int dist;  
    private int[] node;  

    private Pair(int dist, int[] node) {  
        this.dist = dist;  
        this.node = node;  
    }  

    @Override  
    public int compareTo(Pair o) {  
        if (this.dist == o.dist) {  
            if (this.node[Y] == o.node[Y]) {  
                return this.node[X] - o.node[X];  
            }  
            return this.node[Y] - o.node[Y];  
        }  
        return this.dist - o.dist;  
    }  
}

위 코드는 내가 알고리즘을 풀 때 사용했던 코드의 일부이다. 다익스트라 알고리즘을 구현하던 중, 우선순위 큐에 넣는 객체를 Pair라고 정의하여 사용했던 상황이다. 이 때, 우선순위 큐에 들어가기 위해서는 정렬 기준을 객체에 명시했어야 했다. 따라서 가중치(dist)를 기본으로 정렬하되, 만약 가중치가 동일하다면 좌표를 기준으로 오름차순으로 정렬되도록 정의하였다.

만약 가중치 기준으로 내림차순으로 정렬하고 싶으면 return this.dist - o.dist 가 아니라 return o.dist - this.dist로 하면 된다.

만약 여기서 Comparable을 implements하지 않으면 어떻게 될까? int[]는 참조 변수이기 때문에 자바에서 자동으로 정렬을 수행할 수 없어 에러를 뱉어낸다.

Comparator

Comparator 인터페이스는 실질적으로 sort 연산을 수행하는 비교연산자 인터페이스이다. Comparable<T> 인터페이스엔 compareTo(T o)밖에 없었는데, Comparator는 equals()부터 시작해서 많은 비교 연산자 메서드가 있음을 확인할 수 있다.

솔직히 Comparable을 기준으로 사용하는 것을 권장하지만, Comparator를 활용하여도 정렬을 구현할 수 있다. 이것도 마찬가지로 class에서 implement하여 사용할 수 있다.

public class StringLengthComparator implements Comparator<String> {  
    @Override  
    public int compare(String o1, String o2) {  
        int l1 = o1.length();  
        int l2 = o2.length();  
        return l1 - l2;  
    }
}

public void stringLengthSort() {
    Collections.sort(nameList, new StringLengthComparator());
    System.out.println(nameList); // Hi, Java, World, Welcome
}

정렬을 자주 사용할 것 같다면 위처럼 사용하겠지만, 일반적인 경우에는 로직 중 한번 정도 정렬을 하게 된다. 따라서 Comparator를 정렬에 사용하기 위해 일반적으로 사용하는 방법은 Comparator를 익명 inner class의 함수로 정의하여 사용하거나 람다식으로 사용하는 방식을 사용한다.

// 익명 클래스 사용 : 1회성 객체로 사용
Arrays.sort(arr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2; // 오름차순 정렬
        return o2 - o1; // 내림차순 정렬

        // 만약 오버플로우가 날 가능성이 있다면 아래처럼 처리 가능
        return Integer.compare(o1, o2); // 오름차순 정렬
        return Integer.compare(o2, o1); // 내림차순 정렬
    }
})

// 람다 표현식 사용
Collections.sort(list, (o1, o2) -> {
    return o1 - o2;
    return Integer.compare(o1, o2);
})

컴파일된 자바 바이트 코드를 javap로 돌려보면 생성된 자바 바이트 코드를 해석할 수 있도록 영문으로 표기해 주는데, 이를 확인해보면 익명 클래스와 람다를 해석하고 실행하는 과정에 차이가 있으며, 실행 시간은 익명 클래스 함수가 조금 더 빠르다고 한다. 근데 너무 속도에 민감한 경우가 아니라면, 편의상 람다식이 낫지 않나 개인적으로는 생각한다. 참고 : 람다는 동작부터 다르다

마무리

개인적인 의견이지만, Comparator는 구현하는 것에 더 귀찮은 요소가 있는 것 같아서, 만약 사용자 정의 알고리즘으로 정렬하려는 경우가 아니라면 Comparable을 구현해서 사용하면 충분하지 않을까 생각한다.