[JAVA] 정렬 - Arrays, Collections, Comparable, Comparator

Arrays.sort(); -> int[], long[] 와 같은 배열 정렬

알고리즘 문제를 풀다보면 정렬을 해야할 때가 많다. 하지만 정렬할 때마다 항상 방법이 조금씩 바뀌는 느낌이 들어 항상 시간을 잡아 먹었었다. 이 기회에 정렬하는 방법을 제대로 알고 넘어 가자는 생각으로 정리해보겠다.

Arrays vs Collections

정렬을 할 때 Arrays.sort()와 Collections.sort()가 가장 자주 사용된다. 그럼 먼저 이 두개의 차이에 대해 알아보자

Arrays.sort()

먼저 Arrays.sort()는 int[], String[] 와 같은 배열 타입만 정렬 가능하다. 그래서 다음과 같이 int[] 배열을 오름차순 정렬 할 수 있다.

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

Arrays.sort(arr);

하지만 int[] 배열을 내림차순 할 땐 오름차순 후 다음과 같이 순서를 바꾸어 내림차순을 할 순 있지만 Arrays.sort()만으로는 내림차순을 할 수 없다.

for (int i = 0; i < arr.length / 2; i++) {
    int temp = arr[i];
    arr[i] = arr[arr.length - i - 1];
    arr[arr.length - i - 1] = temp;
}

내림차순을 할 수 없는 이유는 아래에 자세하게 정리할 것이지만, 결론만 말하자면 내림차순을 할 땐 Comparable나 Comparator이 필요하기 때문이다. 이 Comparable와 Comparator의 경우는 int나 double 과 같은 data type 이나 primitive type 의 변수가 아닌 Integer, Double와 같은 제네릭 타입이 필요하기 때문이다. 만약 int, Integer의 차이를 모르겠다면 이 블로그를 참고하세요.

따라서 Integer 배열의 경우에는 다음과 같이 오름차순, 내림차순할 수 있다. reverseOrder()은 Collections의 내장 함수로 Collections에 대해선 나중에 알아보자.

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

Arrays.sort(arr);

Arrays.sort(arr, Collections.reverseOrder());
        

Collections.sort()

Collections.sort()읜 경우에는 ArrayList, LinkedList, Stack, Vector 같은 List만 정렬할 수 있다. 이런 List는 Arrays.sort와 비슷하게 다음과 같이 오름차순, 내림차순 할 수 있다.

List<Integer> list = new ArrayList<>();

list.add(2);
list.add(5);

Collections.sort(list); // 오름차순
Collections.sort(list, Collections.reverseOrder()); // 내림차순

/*
더 간단한 내림차순 방법 -> 이유는 추후에 설명
list.sort(Collections.reverseOrder());
*/

Comparable vs Comparator

위에서 Comaprable, Comparator 이 계속해서 언급되었다. 이 두 개의 인터페이스는 왜 계속 언급하고 왜 필요할까?

위에 있던 예제들을 원시타입 이라고 불리는 실수 변수를 가지고 비교하기 때문에 크고 작음을 분명하게 구분하여 정렬을 할 수 있었다. 하지만 class 객체의 배열이나 리스트의 경우에 크고 작음을 명확하게 구분하기 쉽지 않다. 이런 경우 Comparable와 Comparator를 사용하게 되는데 어떻게 사용하는지 살펴보자.

Comparable

먼저 Comparable은 내부에서 정렬 기준을 정의 하는 인터페이스이로 다음과 같이 항상 정렬의 대상이 되는 객체(클래스)에서 참조하여 compareTo(Object o)를 구현해야 한다.

public class Member implements Comparable<Member> {
    private String name;
    private int height;

    @Override
    public int compareTo(Member other) {
        return this.height - other.height; // 키 오름차순 정렬
        // return other.height- this.height; // 키 내림차순 정렬
    }
}

여기서 잘 살펴보면 compareTo의 리턴값을 int이다. 이 리턴 값을 자기 자신을 기준으로 상대방과의 차이가 얼마나 나느냐 에 대한 값으로 양수일 경우 오름차순으로, 음수일 경우 내림차순으로 정렬하게 된다.

이렇게 만들어진 Member의 경우 어떻게 정렬되는지는 아래 사용 방법에서 확인해보자.

Comparator

Compareable의 경우에는 내부에서 정렬기준을 정의 했다면 Comparator은 외부에서 정렬 기준을 제공한다. 정렬 기준이 외부에서 주입되기 때문에 compare(T o1, T o2); 처럼 2개의 기준이 주어진다.

Comparator에서 구현해야할 compare() 다음과 같이 Comparable의 compareTo에서 처럼 자기 자신 대신 o1를 기준으로 상대방과의 차이를 계산해 양수인 경우 오름 차순, 음수인 경우 내림차순이 되는 원리는 똑같다.

Comparator<Member> comparator = new Comparator<Member>() {
            @Override
            public int compare(Member o1, Member o2) {
                return o1.height - o2.height; // 오름차순
//                return o2.height - o1.height; // 내림차순
            }
        }

그리고 Comparator은 위에 @FunctionalInterface어노테이션이 붙은 함수형 인터페이스다. 함수형 인터페이스는 람다식에 사용될 수 있기 때문에 이 역시 사용 방법에서 확인해보자. 또 더 자세한 함수형 인터페이스와 람다식에 대해 알고 싶다면 이 블로그를 참고해보자.

사용 방법

그럼 Arrays, Collections, Comparable, Comparator을 어떻게 사용하는지 간단한 예제로 확인해보자. 먼저 Arrays, Collections에서 정렬 기준으로 Comparable, Comparator모두 사용할 수 있음을 인지하자.

다시 한번 정리하자면 Comparable의 경우 내부에서 정렬 기준을 제공함으로 정렬의 대상이 되는 클래스를 다음과 같이 작성한다.

• Comparable 사용시

public class Member implements Comparable<Member> {
    private String name;
    private int height;
    
    public Member(String name, int height) {
        this.name = name;
    	this.height = height;
    }

    @Override
    public int compareTo(Member other) {
        return this.height - other.height; // 키 오름차순 정렬
        // return other.height- this.height; // 키 내림차순 정렬
    }
}

Comparator의 경우 외부에서 정렬이 제공됨으로 다음과 같이 클래스에서 따로 참조가 필요하지 않다.

• Comparator 사용시

public class Member {
    private String name;
    private int height;
    
    public Member(String name, int height) {
        this.name = name;
    	this.height = height;
    }
}

1. Arrays.sort() - Comparable

Arrays는 배열 타입의 경우에 사용할 수 있으므로 다음과 같이 Member배열을 만들다.

Member[] members = new Member[5];

members[0] = new Member("A", 5);
members[1] = new Member("B", 2);
members[2] = new Member("C", 4);
members[3] = new Member("D", 1);
members[4] = new Member("E", 3);

그리고 Arrays.sort(members); 실해하면 내부적으로 compareTo(Member other)의 내용을 기준으로 오름차순 정렬이 된다.

Arrays.sort(members);

for (int i = 0; i < 5; i++) {
	System.out.println("name : " + members[i].name + ", height : " + members[i].height);
}

• 결과

name : D, height : 1
name : B, height : 2
name : E, height : 3
name : C, height : 4
name : A, height : 5

	@Override
    public int compareTo(Member other) {
        return other.height- this.height; // 키 내림차순 정렬
    }

위와 같이 comapreTo를 바꾸면 다음과 같이 키를 기준으로 내림차순으로 정렬된다.

name : A, height : 5
name : C, height : 4
name : E, height : 3
name : B, height : 2
name : D, height : 1

2. Arrays.sort() - Comparator

Comparator는 외부에서 주입을 해줘야하기 때문에 다음과 같이 Comparator 인스턴스를 따로 만들어 준다.

 		// 외부에서 정렬기준 구현
        Comparator<Member> comparator = new Comparator<Member>() {
            @Override
            public int compare(Member o1, Member o2) {
                return o1.height - o2.height; // 키 오름차순
            }
        };
        
        Arrays.sort(members, comparator); // 정렬 기준 외부에서 제공

        for (int i = 0; i < 5; i++) {
            System.out.println("name : " + members[i].name + ", height : " + members[i].height);
        }

위에서 언급했듯이 Comparator은 함수형 인터페이스로 다음과 람다식으로 간단하게 표현할 수 있다.

Arrays.sort(members, (o1, o2) -> {return o1.height - o2.height;});

3. Collections.sort() - Comparable

Collections.sort()는 List 타입의 경우 정렬이 가능하니 위에서처럼 Comparable를 참조한 클래스를 가지고 다음과 같은 List를 만들었다.

List<Member> memberList = new ArrayList<>();
        
memberList.add(new Member("A", 5));
memberList.add(new Member("B", 2));
memberList.add(new Member("C", 4));
memberList.add(new Member("D", 1));
memberList.add(new Member("E", 3));

Collections.sort(memberList);

for (int i = 0; i < 5; i++) {
	Member temp = memberList.get(i);
    System.out.println("name : " + temp.name + ", height : " + temp.height);
}

그 후 위와 같이 Collections.sort(memberList)를 하면 내부적으로 정해진 compareTo에 따라 다음과 같은 오름차순이 정렬된다.

name : A, height : 5
name : C, height : 4
name : E, height : 3
name : B, height : 2
name : D, height : 1

4. Collections.sort() - Comparator

이 경우 사용 방법 2번과 비슷하게 다은과 같이 사용할 수 있다.

		Comparator<Member> comparator = new Comparator<Member>() {
            @Override
            public int compare(Member o1, Member o2) {
                return o1.height - o2.height;
            }
        };
        
        Collections.sort(memberList, comparator);


        for (int i = 0; i < 5; i++) {
            Member temp = memberList.get(i);
            System.out.println("name : " + temp.name + ", height : " + temp.height);
        }

추가로 Arrays와 Collections를 사용하지 않고 정렬할 수 있는 2가지 방법이 있다. 하지만 이 역시 Comparator를 이해했다면 이해하기 어렵지 않을 것이다.

5. stream().sort()

배열타입의 경우 Arrays.stream(members).sort()으로 배열을 stream을 만든 후 .sort()를 붙여 정렬할 수 있다.

사진 처럼 sort()에는 Comparator 타입의 매개변수가 들어와야 함을 알 수 있다. 그럼 우리는 직접 Comparator를 만들어 .sort(comparator)로 넣던지 람다 표현식을 사용할 수 있다. 여기서는 좀 익숫하지 않을 수 있는 람다식으로 구현하면 다음과 같다.

Arrays.stream(members).sorted((o1, o2) -> {return o1.height - o2.height;});

6. memberList.sort()

List를 보면 다음과 같이 내부적으로 sort()메소드가 있는 것을 확인할 수 있고 매개변수 역시 함수형 인터페이스인 Comparator인 것을 확인할 수 있다.

그럼 이전에 해던 것처럼 람닥식으로 표현한다면 다음과 같다.

memberList.sort(((o1, o2) -> {return o1.height - o2.height;}));

정리

마지막으로 정리를 해보자면 Arrays 는 배열 타입, Collections는 List타입에서 사용된다.
먼저 Arrays, Collections에서 정렬 기준으로는 Comparable, Comparator 2개 모두 사용할 수 있다.

Comparable는 내부에서 정렬기준을 정의함으로 정렬 대상이 되는 클래스에서 참조하여 compareTo(T o)를 구현해야 한다.

Comparator은 외부에서 정렬기준을 정의함으로 클래스는 따로 참조하지 않아도 되고, compare(T o1, T o2)구현해야 한다. 또한 Comparator은 함수형 인터페이스로 람다 표현식으로도 표현할 수 있으니 람다 표현식에 대해 조금 더 알고 싶다면 이 블로그를 참고하자!

Comparable -> compareTo(T o)
Comparator -> compare(T o1, T o2)