TIL - Comparator (09.25)

📚 오늘 공부한 내용 - 정렬 (Comparable & Comparator)

🎯 정렬의 기본 개념

정렬 알고리즘의 동작 원리

정렬은 두 요소를 비교하여 크기에 따라 위치를 바꾸는 과정을 반복합니다.

[3, 2, 1] → 3과 2 비교 → 교환 → [2, 3, 1]
[2, 3, 1] → 3과 1 비교 → 교환 → [2, 1, 3]
[2, 1, 3] → 2와 1 비교 → 교환 → [1, 2, 3]

자바의 정렬 알고리즘

• 기본형 배열: 듀얼 피벗 퀵소트(Dual-Pivot QuickSort)
• 객체 배열: 팀소트(TimSort)
• 평균 성능: O(n log n)

기본 정렬 사용법

Integer[] array = {3, 2, 1};
Arrays.sort(array);  // [1, 2, 3]

List<Integer> list = Arrays.asList(3, 2, 1);
Collections.sort(list);  // 또는 list.sort(null)

---

🔧 두 가지 정렬 방법

Java는 객체 정렬을 위해 두 가지 인터페이스를 제공합니다.

1️⃣ Comparable - 자연 순서(Natural Ordering)

public interface Comparable<T> {
    int compareTo(T o);
}

특징:

• 객체 자체에 정렬 기준을 내장
• 클래스의 기본 정렬 방식 정의
• 자연 순서라고 부름

반환값 규칙:

• 현재 객체 < 비교 객체: 음수(-1) 반환
• 현재 객체 = 비교 객체: 0 반환
• 현재 객체 > 비교 객체: 양수(1) 반환

구현 예시:

public class MyUser implements Comparable<MyUser> {
    private String id;
    private int age;
    
    public MyUser(String id, int age) {
        this.id = id;
        this.age = age;
    }
    
    @Override
    public int compareTo(MyUser o) {
        // 나이를 기준으로 오름차순 정렬
        return this.age < o.age ? -1 : (this.age == o.age ? 0 : 1);
        // 또는 간단히: return Integer.compare(this.age, o.age);
    }
}

2️⃣ Comparator - 별도 정렬 기준

public interface Comparator<T> {
    int compare(T o1, T o2);
}

특징:

• 객체 외부에서 정렬 기준을 제공
• 다양한 정렬 방식을 필요에 따라 선택
• 기본 정렬 외에 추가적인 정렬 기준 제공

반환값 규칙:

• 첫 번째 객체 < 두 번째 객체: 음수(-1) 반환
• 첫 번째 객체 = 두 번째 객체: 0 반환
• 첫 번째 객체 > 두 번째 객체: 양수(1) 반환

구현 예시:

// ID 기준으로 정렬하는 Comparator
public class IdComparator implements Comparator<MyUser> {
    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId());
    }
}

// 나이 내림차순 정렬하는 Comparator  
public class AgeDescComparator implements Comparator<MyUser> {
    @Override
    public int compare(MyUser o1, MyUser o2) {
        return Integer.compare(o2.getAge(), o1.getAge()); // 순서 바뀜
    }
}

---

🎮 정렬 방법 사용법

기본 정렬 (Comparable 사용)

MyUser[] users = {
    new MyUser("a", 30),
    new MyUser("b", 20), 
    new MyUser("c", 10)
};

// 기본 정렬 - Comparable의 compareTo() 사용
Arrays.sort(users);
// 결과: age 기준 오름차순 [c(10), b(20), a(30)]

List<MyUser> userList = Arrays.asList(users);
userList.sort(null);  // null = 기본 정렬 사용

별도 정렬 기준 (Comparator 사용)

// ID 기준으로 정렬
Arrays.sort(users, new IdComparator());
// 결과: id 기준 오름차순 [a(30), b(20), c(10)]

// 나이 내림차순 정렬
Arrays.sort(users, new AgeDescComparator());

// 정렬 순서 뒤집기
Arrays.sort(users, new IdComparator().reversed());

// List에서 사용
userList.sort(new IdComparator());

---

🌳 Tree 구조와 정렬

TreeSet, TreeMap 같은 이진 탐색 트리는 데이터 저장 시 정렬이 필수입니다.

        10
       /  \
      5    15
     / \   / \
    1   6 11 16

왜 정렬이 필수인가?

• 새 데이터를 왼쪽 노드에 저장할지 오른쪽 노드에 저장할지 비교가 필요
• 따라서 Comparable 또는 Comparator가 반드시 필요

TreeSet/TreeMap 사용 예시

// Comparable 사용 - 기본 정렬
TreeSet<MyUser> treeSet1 = new TreeSet<>();
treeSet1.add(new MyUser("c", 10));
treeSet1.add(new MyUser("b", 20)); 
treeSet1.add(new MyUser("a", 30));
// 결과: age 기준 정렬 [c(10), b(20), a(30)]

// Comparator 사용 - 별도 정렬 기준
TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
treeSet2.add(new MyUser("c", 10));
treeSet2.add(new MyUser("b", 20));
treeSet2.add(new MyUser("a", 30));
// 결과: id 기준 정렬 [a(30), b(20), c(10)]

---

⚠️ 주의사항과 오류 처리

필수 구현 체크

// 🚫 Comparable 구현 안 함 + Comparator 제공 안 함
class BadUser {
    private int age;
    // compareTo() 구현 안 함
}

TreeSet<BadUser> set = new TreeSet<>();
set.add(new BadUser()); 
// 💥 ClassCastException 발생!

오류 메시지:

java.lang.ClassCastException: 
class BadUser cannot be cast to class java.lang.Comparable

올바른 해결책

// ✅ 방법 1: Comparable 구현
class GoodUser implements Comparable<GoodUser> {
    @Override
    public int compareTo(GoodUser o) { ... }
}

// ✅ 방법 2: Comparator 제공
TreeSet<BadUser> set = new TreeSet<>(new UserComparator());

---

🎯 Comparable vs Comparator 비교

구분 Comparable Comparator

위치	객체 내부에 구현	객체 외부에서 제공
목적	기본(자연) 정렬 기준	추가적인 정렬 기준
메서드	compareTo(T o)	compare(T o1, T o2)
개수	클래스당 1개만	여러 개 가능
사용	Arrays.sort(array)	Arrays.sort(array, comparator)
우선순위	낮음	높음 (Comparator가 우선)

실무 선택 가이드

• 기본 정렬이 명확한 경우: Comparable 구현 (예: 나이, 이름 등)
• 다양한 정렬이 필요한 경우: Comparator 추가 제공
• 기존 클래스를 수정할 수 없는 경우: Comparator 사용

---

💡 고급 기능들

정렬 순서 뒤집기

// Comparable 기본 정렬의 역순
Arrays.sort(users, Collections.reverseOrder());

// Comparator의 역순  
Arrays.sort(users, new IdComparator().reversed());

메서드 참조와 람다식 (Java 8+)

// 람다식으로 Comparator 구현
users.sort((u1, u2) -> u1.getName().compareTo(u2.getName()));

// 메서드 참조 사용
users.sort(Comparator.comparing(MyUser::getName));
users.sort(Comparator.comparing(MyUser::getAge).reversed());

복합 정렬 기준

// 나이 먼저, 같으면 이름으로 정렬
users.sort(Comparator.comparing(MyUser::getAge)
                    .thenComparing(MyUser::getName));

---

🎯 오늘의 핵심 포인트

1. 두 가지 정렬 방법: Comparable(내부 기준) vs Comparator(외부 기준)
2. 반환값 규칙: 음수, 0, 양수로 대소관계 표현
3. 우선순위: Comparator가 Comparable보다 우선
4. Tree 구조: TreeSet/TreeMap은 정렬 기준이 필수
5. 오류 방지: 둘 중 하나라도 반드시 구현/제공해야 함