⊙ 제목은 뭘로할까?

이 문서는 정렬에 개입하는 두개의 인터페이스인 java.lang.Comparable 과 java.util.Comparator 에 대해서 설명합니다.

이 두가지 인터페이스를 잘 이해하면 아래와 같은 다양한 JDK 구현체들을 손쉽게 이용할 수 있습니다.

* Arrays.sort(..) 메소드를 호출해서 원하는대로 element들을 정렬할 수 있습니다.

* TreeMap과 TreeSet 를 사용할 때 원하는대로 키값들(또는 element들)을 정렬할 수 있습니다.

* 오름차순, 내림차순 정렬을 손쉽게 구현할 수 있습니다.

* 다중 정렬을 구현할 수 있습니다(나이의 오름차순, 키의 내림차순 등으로)

Natural Ordering

java.lang.Comparable 문서를 보면 다음과 같이 쓰여있습니다.

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

(이 인터페이스는 이를 구현하는 클래스의 인스턴스들에게 종합적인 순서를 부여합니다. 이러한 순서는 클래스의 본연本然의 순서라 하고, compareTo 메소드가 본연적 순서를 비교합니다)

말이 묘하게 어렵습니다만, 예를 들어서 natural ordering의 성질을 갖는 대표적인 클래스가 바로 String 입니다.

알파벳이든 한글(가나다..)이든 문자에는 우리 머릿속에서 자연스럽게 떠오르는 순서가 있습니다. 알파벳 B는 알파벳 C보다 앞서고, '주'는 '하'보다 앞섭니다. 이거 이외에 다른 정렬 방식은 딱히 존재하지 않는듯 합니다(내림차순 정렬은 오름 차순의 정반대이므로 사실상 동일한 정렬 방식입니다)

이러한 속성을 갖는 또다른 예가 바로 "숫자들" 입니다.

45는 98보다 앞서고 8은 80보다 앞섭니다. 이렇게 숫자라는 관념의 대상에는 암묵적으로 대다수가 동의하는 순서의 개념이 담겨있습니다. 시간도 숫자로 나타낼 수 있기 때문에 natural ordering의 성질을 갖고 있습니다.

하지만 아래와 같이 학생을 나타내는 클래스에는 모두가 암묵적으로 합의할만한 순서의 개념이 없습니다.

학생을 정렬할때는 이름의 오름차순으로 정렬할 수도 있고 생년월일의 내림차순으로 정렬할 수도 있습니다. 때에 따라서는 전화번호의 오름차순으로 정렬할 수도 있습니다.

애플리케이션의 맥락에 따라서 Student 클래스의 인스턴스들을 줄세우는 방법은 달라집니다.

주어진 클래스가 다양한 속성들(properties)을 포함하고 있으면 natural ordering은 존재하지 않는 경우가 대부분입니다(물론 정책적으로 natural ordering을 규정할 수는 있겠습니다. 예를 들어 위의 Student 클래스는 학번을 natural ordering의 기준으로 합의하는 식)

어떤 클래스에 본연의 순서 개념이 녹아있는 경우, java.lang.Comparable 인터페이스를 구현하면 JDK에서 제공하는 다양한 구현체들의 정렬 및 비교 기능들을 손쉽게 이용할 수 있습니다.

그래서 java.lang.String 클래스나 Integer, Long과같은 숫자 클래스들처럼 natural ordering의 성질을 갖는 클래스들은 예외없이 Comparable 인터페이스를 구현하고 있습니다. 이때문에 Comparable 인터페이스도 String, Integer 와 같이 java.lang 패키지에 속해 있습니다.

Comparable.compareTo(...)

그리고 이 본연의 순서를 비교하는 method가 compareTo입니다.

java.lang.Integer 클래스의 compareTo 구현은 아래와 같습니다.

아래와 같이 두 숫자를 비교하는 경우

this.value 는 변수 two의 값이고, anotherInteger.value는 변수 five의 값을 의미합니다.

compare(int, int) 메소드에서는 왼쪽숫자(two)가 오른쪽 숫자(five)보다

작으면 -1을 반환하고 

같으면 0을 반환하고

크면 +1을 반환합니다.

Comparable.comapreTo(..) method는 int값을 반환하는데 예를 들어서 a.compareTo(b)의 반환값이 음수라면 

1) 음수: 기준값(왼쪽값)인 a가 비교값(오른쪽값) b보다 순서상으로 먼저임!

..을 나타냅니다(a가 순서상으로 앞선다, a가 b 앞에 등장해야함을 나타냅니다)

a.compareTo(b)의 반환값이 양수라면

2) 양수: 기준값(왼쪽값)인 a가 비교값(오른쪽값) b보다 순서상으로 나중임!

..을 나타냅니다. 다시 말해서 b가 a보다 먼저 등장한다, b가 순서상으로 a보다 앞선다라는 뜻이 됩니다.

a.compareTo(b)의 반환값이 0이라면

3) zero : 기준값(왼쪽값)인 a와 비교값(오른쪽값) b은 순서가 같음!

..을 나타냅니다. 즉, a와 b는 순서가 동일하므로 둘 중에 누가 앞에 나오든 상관이 없다는 뜻이 됩니다.

이러한 순서의 개념은 "정렬" 기능에서 가장 빈번히 사용됩니다.

JDK에서는 Arrays.sort(Object[]) 메소드가 주어진 배열의 원소들을 정렬해주는데, 이때 배열에 담긴 인스턴스의 실제 클래스는 반드시 Comparable 인터페이스를 구현해야 합니다.

정렬 구현체에서는 배열의 각 원소들에 대해서 compareTo 메소드를 호출한 반환값(음수, 0, 양수)을 이용해서 주어진 두 원소의 위치를 서로 바꿀지를 결정합니다.

JDK에 구현된 정렬 알고리즘은 평균적인 프로그래머가 되는대로 작성한 정렬 알고리즘보다 우수합니다. 하지만 정렬 알고리즘에서는 임의의 두 원소 중 누가 더 순서상 앞서는지 판단할 수 없습니다. 정렬 대상이 int, long과 같은 숫자라면 비교 연산자 <, > 등으로 natural ordering을 판별할 수 있지만 인스턴스에 대해서는 이러한 연산자를 적용할 수 없습니다. 또한 주어진 원소들을 정렬하는 기능과 각 원소들의 우선순위를 판별하는 기능은 서로 분리해야 정렬 알고리즘을 재사용할 수 있기때문에 "원소의 순서를 정하는 구현"을 정렬 알고리즘에서 따로 떼어내는 것이 합리적입니다(오름차순, 내림차순을 생각해봅시다).

사용자는 정렬 알고리즘에게 주어진 두 원소 a, b에 대해서 "a가 먼저 등장해야 한다" 라든가 "b가 앞선다"라거나 "a와 b는 순서가 똑같다"라고 알려줘야 하고 Comparable.compareTo(..) 메소드의 반환값이 그 역할을 합니다(정렬 알고리즘에게 힌트를 제공해줌).

java.util.Comparator

하지만 애플리케이션을 구성하는 수많은 클래스들중에 정렬이 필요한 타입들에 대해서 일일이 Comparable 구현을 넣어주기 위해서 정렬하고 싶은 클래스를 상속받아서 하위 클래스를 전개하는 상황 역시 배보다 배꼽이 커지는 꼴입니다.

또는 합의된 natural ordering 이 없거나 그때그때 정렬의 기준이 달라지는 클래스에 대해서는 함부로 Comparable 구현을 집어넣으면 매번 코드를 수정해야 하는 이상하고 번거로운 상황이 펄쳐집니다.

이런 상황에서도 JDK의 정렬 구현을 이용할 수 있도록 java.util.Comparator를 제공하고 있습니다.

Comparator 는 Comparable과 사용 방법이 거의 유사합니다.

Comparable이 이를 구현한 타입의 인스턴스에 대해서 a.compareTo(b) 와 같이 호출한다면 Comparator는 cmp.compare(a, b)와 같이 사용합니다. Comparator.compare(a, b)도 int 타입의 값을 반환하고, 이 값의 의미는 Comparable.compareTo(..) 와 동일합니다.

Comparator.compare(a,b) 의 반환값이

1) 0보다 작으면 a가 b보다 순서상으로 앞서야 함

2) 0이면 둘중에 누가 앞서든 상관없음

3) 0보다 크면 b가 a보다 순서상으로 앞서야 함

내림차순 정렬

인터페이스 java.lang.Comparable을 구현하고 있는 String 의 기본 정렬은 "오름차순" 정렬입니다(A가 D보다 먼저, D가 H보다 먼저... Z는 맨 끝)

java.util.Comparator 구현체를 추가하면 손쉽게 문자열을 내림차순으로(order by descending) 정렬할 수 있습니다.

람다표현식으로는 아래와 같이 간단하게 코딩할 수 있습니다.

또는 곧바로 sort 메소드의 인자로 구현체를 넘길 수도 있습니다.

어쨋든 코드를 실행하면 아래와 같이 내림차순으로 이름들이 출력됩니다.

[TOM, JANE, JACK, APRIL]

String에 기본 구현된 compareTo(...) 메소드의 반환값에 -1을 곱해줌으로써 오름차순을 내림차순으로 변경합니다.  a와 b의 위치를 바꿔서 호출하면 -1을 곱한 것과 같은 효과가 발생합니다.

(JDK의 Collections.reverseOrder() 와 같은 구현에서 위처럼 a,b를 바꿔 호출함으로써 내림차순 정렬을 구현하고 있습니다. 개인적으로는 -1을 곱해서 내림차순임을 알아보기 쉽게 코딩하는 쪽을 선호합니다.)

홀짝 정렬

주어진 자연수들을 정렬할때 홀수는 짝수보다 먼저 나오게 하고 싶습니다(홀수끼리 또는 짝수끼리는 정렬될 필요는 없습니다)

아래와 같이 홀짝만 판별하는 Comparator구현체를 만들어서 홀짝 정렬을 할 수 있습니다.

주어진 수 a, b 둘다 짝수이거나 홀수이면 if(oddA == oddB) 0을 반환합니다. 0을 반환함으로써 정렬 알고리즘에게 "둘다 홀수이면(짝수이면) 굳이 두 숫자의 위치를 바꿀 필요 없음"이라고 힌트를 제공해줍니다.

a가 홀수이면 -1을 반환해서 왼쪽값인 a(홀수)가 오른쪽값인 b(짝수)보다 앞서야 한다고 알려줍니다.

a가 짝수이면 반대로 양수 1을 반환해서 오른쪽값인 b(홀수)가 먼저 등장하게 합니다.

다음글 https://javafreak.tistory.com/273