정렬하는 간단한 문제.
C++에서는 O(n log n) 정렬을 std::sort() 함수로 지원하는데,
자바에서는 Collections.sort(), Arrays.sort() 를 지원한다.
-
Collections.sort()
컬렉션 프레임워크의List인터페이스를 구현한 모든 컬렉션(ArrayList,LinkedList등) 에 적용 가능하다. -
Arrays.sort()
배열에 적용가능.
공통점
두 메서드 모두 기본적으로 오름차순 정렬이다. 또한 Comparator 인터페이스를 활용한 커스텀 정렬이 가능하다.
Comparator 인터페이스
자바에서 정렬 순서를 정의하기 위한 인터페이스. 기본적으로는 Comparator 인터페이스를 구현하고,
compare()메서드를 오버라이딩 하면 된다.
compare(T o1, T o2)
: 두 객체 o1과 o2를 비교하는 메서드로, 이 메서드를 통해 정렬 기준을 정의한다. 반환값에 따라 두 객체의 순서가 결정된다.
- 반환값이 양수이면 o1이 o2보다 크다고 판단.
- 반환값이 음수이면 o1이 o2보다 작다고 판단.
- 반환값이 0이면 두 객체가 같다고 판단.
//Integer.compare
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}예시로 Integer.compare() 메서드는 위와 같이 작성되어있다.
오름차순으로 정렬된다.
공식문서
다시 한 번 공식문서를 읽는 즐거운 시간
공식문서를 읽으면서 배우는 것이 참 많다. 특히 인텔리제이에서 컬렉션 프레임워크 상속/구현 관계를 쭉쭉 올라가면 전체적인 구조가 감이 잡힌다.
-
Comparator는 또한
sorted sets,sorted maps같은 특정 자료구조들의 정렬을 컨트롤 할 수 있다.
: 정렬의 일관성이 보장되지 않으면, "strangely" 하게 작동할 수 있다 (밑에서 설명) -
일반적으로 Comparator는
java.io.Serializable을 구현하는 것이 좋다. 특정 자료구조(TreeSet,TreeMap등)가 직렬화에 성공하려면, 그 자료구조의 정렬에 사용된 Comparator 또한 직렬화가 가능해야하기 때문이다.
Comparator 사용 시 주의점
Comparator 를 사용하여 sorted set 과 sorted map을 정렬할 때는,
정렬의 일관성을 유지해야한다.
정렬의 일관성은, Comparator c 에 대해
c.compare(e1, e2)==0 과 e1.equals(e2)의 boolean 값이 동일한 상황을 의미한다.
왜 둘이 동일해야하는가? SortedMap의 구현체인
TreeMap의 put() 메서드에서 확인할 수 있다.
//TreeMap.java
public V put(K key, V value) {
//생략...
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//생략...
}TreeMap은 내부적으로 레드블랙트리로 이루어져있고, 삽입 과정에서 초기화 시점에 설정된 Comparator를 통해 대소 비교 및 equality를 확인하는 것을 알 수 있다.
즉, c.compare(e1, e2) != 0 을 만족한다면, TreeMap은 두 객체가 서로 다르다고 판단하는 것이다.
이러한 상황에서 e1.equls(e2) && c.compare(e1, e2) != 0 를 만족하는 일관성이 깨지는 상황은 Set.add() 와 같은 상위 인터페이스의 명세 조건(general contract)을 위반하게 된다.
Set 인터페이스의 contains 메서드 설명을 보면, Objects.equals() 가 true일 때 중복된 원소임을 판단한다고 작성되어있다.
