Java Sorting

devK08·2026년 1월 6일
Javasorting

Sorting 알고리즘 개념 정리

1. 정렬이란?

데이터를 특정 순서로 재배열하는 작업입니다.

왜 필요한가?

검색 성능 향상

정렬 안 된 배열: [5, 2, 8, 1, 9]
"1" 찾기 → 처음부터 끝까지 순회 → O(n)

정렬된 배열: [1, 2, 5, 8, 9]
"1" 찾기 → 이진 탐색 → O(log n)

데이터 분석

  • 최댓값/최솟값 쉽게 찾기
  • 중앙값 계산
  • 중복 데이터 제거 (인접 요소 비교)

사용자 경험

  • 가격순, 이름순, 날짜순 정렬
  • 검색 결과 랭킹

2. 정렬 알고리즘 분류

비교 기반 정렬

요소끼리 비교하여 정렬

Bubble Sort, Selection Sort, Insertion Sort
Merge Sort, Quick Sort, Heap Sort, Tim Sort

비교하지 않는 정렬

값의 분포를 이용하여 정렬

Counting Sort, Radix Sort, Bucket Sort

3. 주요 정렬 알고리즘

Bubble Sort (버블 정렬)

원리: 인접한 두 요소를 비교하며 큰 값을 뒤로 보냄

[5, 2, 8, 1]

1단계: 5 vs 2 → [2, 5, 8, 1]
       5 vs 8 → [2, 5, 8, 1]
       8 vs 1 → [2, 5, 1, 8]  ← 8이 끝으로

2단계: 2 vs 5 → [2, 5, 1, 8]
       5 vs 1 → [2, 1, 5, 8]  ← 5가 끝-1로

3단계: 2 vs 1 → [1, 2, 5, 8]  ← 완료!

특징

  • 시간복잡도: O(n²)
  • 공간복잡도: O(1)
  • 안정성: ✅
  • 사용: 거의 없음

Selection Sort (선택 정렬)

원리: 최솟값을 찾아 맨 앞과 교환

[5, 2, 8, 1]

1단계: 최솟값 1 찾기 → [1, 2, 8, 5]
2단계: 최솟값 2 찾기 → [1, 2, 8, 5]
3단계: 최솟값 5 찾기 → [1, 2, 5, 8]
완료!

특징

  • 시간복잡도: O(n²)
  • 공간복잡도: O(1)
  • 안정성: ❌
  • 사용: 거의 없음

Insertion Sort (삽입 정렬)

원리: 왼쪽은 정렬된 상태 유지하며, 새 요소를 적절한 위치에 삽입

[5, 2, 8, 1]

1단계: [5] | 2, 8, 1  → 2를 삽입 → [2, 5] | 8, 1
2단계: [2, 5] | 8, 1  → 8을 삽입 → [2, 5, 8] | 1
3단계: [2, 5, 8] | 1  → 1을 삽입 → [1, 2, 5, 8]

특징

  • 시간복잡도: 평균 O(n²), 최선 O(n)
  • 공간복잡도: O(1)
  • 안정성: ✅
  • 사용: 작은 배열, 거의 정렬된 배열

Merge Sort (병합 정렬)

원리: 분할 정복 - 반으로 나누고, 정렬하고, 합치기

[5, 2, 8, 1]

분할:
[5, 2, 8, 1]
[5, 2] [8, 1]
[5] [2] [8] [1]

병합:
[2, 5] [1, 8]
[1, 2, 5, 8]

병합 과정

[2, 5]와 [1, 8]을 병합

비교: 2 vs 1 → [1]
비교: 2 vs 8 → [1, 2]
비교: 5 vs 8 → [1, 2, 5]
남은 요소    → [1, 2, 5, 8]

특징

  • 시간복잡도: O(n log n) (모든 경우)
  • 공간복잡도: O(n)
  • 안정성: ✅
  • 사용: 안정 정렬 필요 시

Quick Sort (퀵 정렬)

원리: 피벗 선택 후 작은 값은 왼쪽, 큰 값은 오른쪽

[5, 2, 8, 1, 9]  피벗=5

1단계: 분할
[2, 1] 5 [8, 9]

2단계: 왼쪽 [2, 1] 정렬  피벗=2
[1] 2 []

3단계: 오른쪽 [8, 9] 정렬  피벗=8
[] 8 [9]

최종: [1, 2, 5, 8, 9]

특징

  • 시간복잡도: 평균 O(n log n), 최악 O(n²)
  • 공간복잡도: O(log n)
  • 안정성: ❌
  • 사용: 가장 빠름 (평균), 실무에서 많이 사용

Heap Sort (힙 정렬)

원리: Max Heap 구성 후, 루트를 반복 추출

[5, 2, 8, 1]

1. Max Heap 구성
       8
      / \
     5   2
    /
   1

2. 루트(8) 추출 → [1, 2, 5] | 8
3. Heapify → 5가 루트
4. 루트(5) 추출 → [1, 2] | 5, 8
5. 반복 → [1, 2, 5, 8]

특징

  • 시간복잡도: O(n log n) (모든 경우)
  • 공간복잡도: O(1)
  • 안정성: ❌
  • 사용: 메모리 제약 환경

Tim Sort (팀 정렬)

원리: Merge Sort + Insertion Sort + 최적화

[1, 2, 3, 10, 9, 8, 15, 16, 17]

1. Run 찾기 (이미 정렬된 부분)
Run1: [1, 2, 3]
Run2: [10, 9, 8] → 역순 감지 → [8, 9, 10]
Run3: [15, 16, 17]

2. Run들을 Merge
[1, 2, 3] + [8, 9, 10] → [1, 2, 3, 8, 9, 10]
[1, 2, 3, 8, 9, 10] + [15, 16, 17] → [1, 2, 3, 8, 9, 10, 15, 16, 17]

특징

  • 시간복잡도: 최선 O(n), 평균/최악 O(n log n)
  • 공간복잡도: O(n)
  • 안정성: ✅
  • 사용: Python, Java (Object 배열), Android

왜 빠른가?

  • 실제 데이터는 부분 정렬 많음
  • 이런 패턴을 활용하여 최적화

4. 성능 비교

시간 복잡도

알고리즘최선평균최악공간안정성
Bubble SortO(n)O(n²)O(n²)O(1)✅
Selection SortO(n²)O(n²)O(n²)O(1)❌
Insertion SortO(n)O(n²)O(n²)O(1)✅
Merge SortO(n log n)O(n log n)O(n log n)O(n)✅
Quick SortO(n log n)O(n log n)O(n²)O(log n)❌
Heap SortO(n log n)O(n log n)O(n log n)O(1)❌
Tim SortO(n)O(n log n)O(n log n)O(n)✅

실제 성능 (100만 건)

Random Data:
Quick Sort:     100ms  ⭐
Tim Sort:       120ms
Merge Sort:     180ms
Heap Sort:      250ms
Insertion Sort: 30,000ms

Already Sorted:
Tim Sort:       15ms   ⭐⭐⭐
Insertion Sort: 20ms
Quick Sort:     100ms
Merge Sort:     180ms

Reversed:
Tim Sort:       25ms   ⭐⭐
Quick Sort:     100ms
Merge Sort:     180ms

5. 안정성(Stability) 개념

정의

같은 값(동일한 키)을 가진 요소들의 원래 순서가 정렬 후에도 유지되는지 여부

입력: [5A, 3, 5B, 1]  (5A가 5B보다 먼저 입력됨)

안정 정렬 (Stable):
출력: [1, 3, 5A, 5B]  ← 5A가 5B보다 앞 ✅

불안정 정렬 (Unstable):
출력: [1, 3, 5B, 5A]  ← 순서 바뀜 ❌

왜 중요한가?

1. 다중 정렬 (Multiple Sorting)

// 학생 데이터
Student("Alice", 25, "IT")      // 입력 순서 1
Student("Bob", 25, "HR")        // 입력 순서 2
Student("Charlie", 25, "IT")    // 입력 순서 3
Student("David", 30, "HR")      // 입력 순서 4

// 1차: 부서로 정렬
[("Alice", 25, "HR"), ("Bob", 25, "HR"), ("Charlie", 25, "IT"), ("David", 30, "IT")]

// 2차: 나이로 정렬 (안정 정렬 사용)
안정 정렬:
[("Alice", 25, "HR"), ("Bob", 25, "HR"), ("Charlie", 25, "IT"), ("David", 30, "IT")]
→ 같은 나이(25) 내에서 부서 순서 유지! ✅

불안정 정렬:
[("Bob", 25, "HR"), ("Charlie", 25, "IT"), ("Alice", 25, "HR"), ("David", 30, "IT")]
→ 같은 나이(25) 내에서 부서 순서 섞임! ❌

2. 데이터베이스 정렬

-- 먼저 이름순 정렬 후, 나이순 정렬
SELECT * FROM users
ORDER BY name;  -- 1차 정렬

SELECT * FROM users
ORDER BY age;   -- 2차 정렬

-- 안정 정렬이면 같은 나이 내에서 이름순 유지
-- 불안정 정렬이면 이름순 무시됨

3. 실무 예제

// 주문 데이터
Order(id=1, date="2024-01-01", amount=1000)
Order(id=2, date="2024-01-01", amount=500)
Order(id=3, date="2024-01-02", amount=1500)

// 먼저 금액순 정렬
orders.sort(Comparator.comparing(Order::getAmount));

// 그 다음 날짜순 정렬 (안정 정렬)
orders.sort(Comparator.comparing(Order::getDate));

// 결과 (안정 정렬):
// 2024-01-01: id=2 (500원), id=1 (1000원)  ← 금액순 유지!
// 2024-01-02: id=3 (1500원)

// 결과 (불안정 정렬):
// 2024-01-01: id=1 (1000원), id=2 (500원)  ← 금액순 무시됨!

안정 정렬 vs 불안정 정렬

안정 정렬 (Stable Sort)

알고리즘:

  • ✅ Merge Sort
  • ✅ Tim Sort
  • ✅ Insertion Sort
  • ✅ Bubble Sort
  • ✅ Counting Sort
  • ✅ Radix Sort

특징:

// 같은 값의 순서 보장
[5A, 3, 5B, 1] → [1, 3, 5A, 5B]
                        ↑    ↑
                    원래 순서 유지

사용 케이스:

  • 객체 정렬 (여러 필드)
  • 다중 정렬 필요
  • 데이터 순서가 의미 있는 경우

불안정 정렬 (Unstable Sort)

알고리즘:

  • ❌ Quick Sort
  • ❌ Heap Sort
  • ❌ Selection Sort

특징:

// 같은 값의 순서 보장 안 됨
[5A, 3, 5B, 1] → [1, 3, 5B, 5A]
                        ↑    ↑
                    순서 바뀔 수 있음

사용 케이스:

  • Primitive Type 정렬 (int, double)
  • 순서가 중요하지 않은 경우
  • 성능이 최우선인 경우

왜 일부 알고리즘은 불안정한가?

Quick Sort가 불안정한 이유

[5A, 3, 5B, 1, 9]  피벗=5A

1단계: 피벗 기준 분할
[3, 1] 5A [5B, 9]

2단계: 피벗을 올바른 위치로 이동
[3, 1, 5A, 5B, 9]

// 문제: 5B가 5A 뒤로 이동
// 하지만 다른 피벗 선택 시 순서 바뀔 수 있음

[5A, 3, 5B, 1, 9]  피벗=5B

[3, 1] 5B [5A, 9]  ← 5A와 5B 순서 바뀜!

Heap Sort가 불안정한 이유

[5A, 3, 5B, 1]

Max Heap 구성:
       5B
      /  \
    5A    3
   /
  1

// 5B가 루트에 올라감 (원래는 5A가 먼저였음)
// Heap 구조 특성상 순서 보장 안 됨

Selection Sort가 불안정한 이유

[5A, 5B, 1]

1단계: 최솟값 1 찾기 → 5A와 교환
[1, 5B, 5A]  ← 5A와 5B 순서 바뀜!

안정성 확인 방법

public class StabilityTest {
    static class Person {
        String name;
        int age;
        int originalIndex;  // 원래 순서 추적
        
        Person(String name, int age, int index) {
            this.name = name;
            this.age = age;
            this.originalIndex = index;
        }
    }
    
    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 25, 0),
            new Person("Bob", 25, 1),
            new Person("Charlie", 25, 2)
        };
        
        // 나이로 정렬
        Arrays.sort(people, Comparator.comparingInt(p -> p.age));
        
        // 안정성 확인
        for (int i = 0; i < people.length - 1; i++) {
            if (people[i].age == people[i + 1].age) {
                boolean stable = people[i].originalIndex < people[i + 1].originalIndex;
                System.out.println("안정 정렬: " + stable);
            }
        }
    }
}

Java에서의 안정성

Arrays.sort()

// Primitive Type (int, double 등): 불안정
int[] arr = {5, 3, 5, 1};
Arrays.sort(arr);  // Dual-Pivot Quick Sort (불안정)

// Object Type: 안정
Integer[] arr = {5, 3, 5, 1};
Arrays.sort(arr);  // Tim Sort (안정)

이유:

Primitive Type:
- 값 자체만 존재 (5는 그냥 5)
- 순서 의미 없음 → 속도 우선 → Quick Sort

Object Type:
- 여러 필드 보유 가능
- 순서 의미 있음 → 안정성 우선 → Tim Sort

Collections.sort()

List<Integer> list = Arrays.asList(5, 3, 5, 1);
Collections.sort(list);  // Tim Sort (안정)

안정 정렬 만들기

불안정 정렬을 안정하게 만드는 방법:

// 원본 인덱스를 함께 저장
class Element {
    int value;
    int originalIndex;
    
    Element(int value, int index) {
        this.value = value;
        this.originalIndex = index;
    }
}

// 정렬 시 값이 같으면 원본 인덱스 비교
Arrays.sort(elements, (a, b) -> {
    if (a.value != b.value) {
        return Integer.compare(a.value, b.value);
    }
    return Integer.compare(a.originalIndex, b.originalIndex);
});

핵심 정리

안정 정렬:

  • ✅ Merge Sort, Tim Sort, Insertion Sort, Bubble Sort
  • ✅ 같은 값의 순서 유지
  • ✅ 객체 정렬, 다중 정렬에 필수
  • ✅ Java Object 배열 기본

불안정 정렬:

  • ❌ Quick Sort, Heap Sort, Selection Sort
  • ❌ 같은 값의 순서 보장 안 됨
  • ✅ 속도 빠름
  • ✅ Java Primitive 배열 기본

선택 기준:

객체 정렬? → 안정 정렬 (Tim Sort)
Primitive 정렬? → 불안정 정렬 (Quick Sort)
다중 정렬? → 안정 정렬 필수
순서 무관? → 불안정 정렬 (더 빠름)

In-Place 정렬 개념

정의

추가 메모리(배열)를 거의 사용하지 않고, 원본 배열 내에서 직접 정렬하는 방식

In-Place:
원본: [5, 2, 8, 1]
    ↓ 배열 내부에서 swap
결과: [1, 2, 5, 8]
추가 메모리: O(1)

Not In-Place:
원본: [5, 2, 8, 1]
    ↓ 새 배열 생성
임시: [1, 2, 5, 8]
    ↓ 복사
결과: [1, 2, 5, 8]
추가 메모리: O(n)

In-Place 정렬 예시

Quick Sort

[5, 2, 8, 1, 9]  피벗=5

피벗보다 작은 값을 왼쪽으로 swap:
[2, 1, 5, 8, 9]  ← 배열 내부에서 교환

왼쪽 [2, 1] 재귀 정렬:
[1, 2, 5, 8, 9]  ← 또 배열 내부에서 교환

추가 메모리: 재귀 스택만 O(log n)

코드:

// In-Place swap! 추가 배열 없음
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

Not In-Place 정렬 예시

Merge Sort

[5, 2, 8, 1]

분할:
[5, 2] [8, 1]

병합 - 새 배열 필요!
int[] temp = new int[2];  ← O(n) 메모리
[2, 5] [1, 8]

최종 병합 - 또 새 배열!
int[] temp = new int[4];  ← O(n) 메모리
[1, 2, 5, 8]

추가 메모리: O(n)

코드:

// Not In-Place: 임시 배열 생성!
int[] temp = new int[right - left + 1];
// 임시 배열에 복사 후 원본에 다시 복사

공간 복잡도 비교

알고리즘In-Place?공간 복잡도
Quick Sort✅O(log n)
Heap Sort✅O(1)
Insertion Sort✅O(1)
Merge Sort❌O(n)
Tim Sort❌O(n)
Counting Sort❌O(n + k)

왜 In-Place가 중요한가?

메모리 절약

// 1억 개 int 정렬

In-Place (Quick Sort):
- 원본: 400MB
- 추가: 거의 없음
- 총: ~400MB

Not In-Place (Merge Sort):
- 원본: 400MB
- 임시 배열: 400MB
- 총: ~800MB  ← 2배!

메모리 제약 환경

// 임베디드, IoT, 모바일
- RAM: 512MB
- 데이터: 300MB

In-Place: 가능 ✅
Not In-Place: 메모리 부족! ❌

성능

Not In-Place:
1. 새 배열 할당 (느림)
2. 데이터 복사 (느림)
3. 가비지 컬렉션 (느림)

In-Place:
1. 배열 내부 swap (빠름)

Trade-off

✅ 장점

1. 메모리 효율적
   - O(1) or O(log n) 공간만 사용

2. 빠름
   - 메모리 할당/복사 오버헤드 없음

3. 대용량 데이터 가능
   - 메모리 부족 걱정 없음

❌ 단점

1. 안정성 보장 어려움
   - Quick Sort, Heap Sort 등 불안정

2. 병렬화 어려움
   - 같은 배열 동시 접근

3. 구현 복잡
   - Swap 로직 복잡

언제 사용하나?

✅ In-Place 사용

1. 메모리 제약 환경
   - 임베디드, IoT, 모바일

2. 대용량 데이터
   - 수 GB 이상

3. Primitive Type
   - int[], double[]
   - 안정성 불필요

4. 성능 최우선

❌ Not In-Place 사용

1. 안정 정렬 필요
   - 객체 정렬
   - 다중 정렬

2. 메모리 여유
   - 서버, PC 환경

3. 병렬 처리
   - 멀티스레드 정렬

4. 간단한 구현

핵심 정리

In-Place

✅ 원본 배열 내에서 직접 정렬
✅ 추가 메모리 거의 없음 (O(1) or O(log n))
✅ Quick Sort, Heap Sort, Insertion Sort
✅ 메모리 효율, 빠름, 대용량 가능
❌ 안정성 보장 어려움

Not In-Place

❌ 임시 배열 생성
❌ 추가 메모리 많이 사용 (O(n))
❌ Merge Sort, Tim Sort, Counting Sort
✅ 안정 정렬 가능
❌ 메모리 많이 사용

선택 기준

메모리 제약? → In-Place
안정성 필요? → Not In-Place
Primitive? → In-Place
Object? → Not In-Place

7. 알고리즘 선택 가이드

데이터 크기별

매우 작음 (< 10):
→ Insertion Sort (간단, 오버헤드 없음)

작음 (< 50):
→ Insertion Sort

중간 (50 ~ 10,000):
→ Quick Sort (빠름)

큼 (10,000+):
→ Tim Sort (안정), Quick Sort (불안정 가능)

데이터 상태별

거의 정렬됨:
→ Tim Sort, Insertion Sort (O(n)에 가까움)

완전 랜덤:
→ Quick Sort (가장 빠름)

역순:
→ Tim Sort (역순 감지 후 뒤집기)

요구사항별

안정성 필요:
→ Merge Sort, Tim Sort

메모리 제약:
→ Heap Sort (O(1) 공간)

최악의 경우 보장:
→ Merge Sort, Heap Sort (O(n log n) 보장)

평균 속도 최우선:
→ Quick Sort

8. Java에서의 정렬

Arrays.sort() - Primitive Type

알고리즘: Dual-Pivot Quick Sort

int[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr);
// [1, 2, 5, 8, 9]

특징

  • 평균: O(n log n)
  • 최악: O(n²) (매우 드뭄)
  • 공간: O(log n)
  • 안정성: ❌

왜 Quick Sort?

Primitive Type (int, double):
- 값 자체만 존재
- 5는 그냥 5 (구별 불가능)
- 안정성 불필요 → 속도 우선!

Arrays.sort() - Object Type

알고리즘: Tim Sort

String[] arr = {"Charlie", "Alice", "Bob"};
Arrays.sort(arr);
// ["Alice", "Bob", "Charlie"]

특징

  • 평균: O(n log n)
  • 최선: O(n) (정렬된 경우)
  • 공간: O(n)
  • 안정성: ✅

왜 Tim Sort?

Object Type:
- 객체는 여러 필드 보유
- 같은 값이어도 다른 객체
- 안정성 중요!

예: User("Alice", 25), User("Bob", 25)
→ 나이로 정렬 시 입력 순서 유지 필요

Collections.sort()

알고리즘: Tim Sort (Arrays.sort(Object[])와 동일)

List<Integer> list = Arrays.asList(5, 2, 8, 1, 9);
Collections.sort(list);
// [1, 2, 5, 8, 9]

내부 동작

public static <T> void sort(List<T> list) {
    Object[] a = list.toArray();     // List → 배열
    Arrays.sort(a);                  // Tim Sort
    // 배열 → List 복사
}

Stream.sorted()

알고리즘: Tim Sort

List<Integer> sorted = list.stream()
    .sorted()
    .collect(Collectors.toList());

9. Comparator & Comparable

왜 필요한가?

// 숫자는 자동으로 정렬 가능
int[] numbers = {5, 2, 8, 1};
Arrays.sort(numbers);  // [1, 2, 5, 8]

// 하지만 객체는?
Student[] students = {
    new Student("Alice", 25),
    new Student("Bob", 20),
    new Student("Charlie", 30)
};
Arrays.sort(students);  // ❌ 에러! 어떻게 비교할지 모름

// 나이순? 이름순? 학번순?

해결책:

  • Comparable: 클래스 내부에 "기본 정렬 기준" 정의
  • Comparator: 외부에서 "다양한 정렬 기준" 정의

Comparable 인터페이스

클래스 자체에 기본 정렬 기준을 부여

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

기본 사용법

public class Student implements Comparable<Student> {
    private String name;
    private int age;
    
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareTo(Student other) {
        // 나이 기준 오름차순
        return Integer.compare(this.age, other.age);
    }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

// 사용
Student[] students = {
    new Student("Alice", 25),
    new Student("Bob", 20),
    new Student("Charlie", 30)
};

Arrays.sort(students);  // compareTo() 사용
System.out.println(Arrays.toString(students));
// 출력: [Bob(20), Alice(25), Charlie(30)]

compareTo() 리턴값 규칙

compareTo(other) 리턴값:

음수 (< 0): this < other  → this를 앞에 배치
0:          this == other → 순서 유지
양수 (> 0): this > other  → this를 뒤에 배치

다양한 비교 방법

// 1. 오름차순
@Override
public int compareTo(Student other) {
    return Integer.compare(this.age, other.age);
}

// 2. 내림차순
@Override
public int compareTo(Student other) {
    return Integer.compare(other.age, this.age);
}

// 3. 문자열 비교
@Override
public int compareTo(Student other) {
    return this.name.compareTo(other.name);
}

// 4. 복합 비교
@Override
public int compareTo(Student other) {
    // 1차: 나이 오름차순
    int ageCompare = Integer.compare(this.age, other.age);
    if (ageCompare != 0) {
        return ageCompare;
    }
    // 2차: 이름 오름차순 (나이가 같을 때)
    return this.name.compareTo(other.name);
}

Comparator 인터페이스

외부에서 다양한 정렬 기준을 정의

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

방법 1: 익명 클래스

Student[] students = {
    new Student("Alice", 25, 85),
    new Student("Bob", 20, 92),
    new Student("Charlie", 30, 78)
};

// 나이순 정렬
Arrays.sort(students, new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return Integer.compare(s1.getAge(), s2.getAge());
    }
});

방법 2: Lambda 표현식

// 나이순
Arrays.sort(students, (s1, s2) -> Integer.compare(s1.getAge(), s2.getAge()));

// 점수순
Arrays.sort(students, (s1, s2) -> Integer.compare(s1.getScore(), s2.getScore()));

// 이름순
Arrays.sort(students, (s1, s2) -> s1.getName().compareTo(s2.getName()));

방법 3: Comparator 메서드 (가장 권장!)

// 나이순
Arrays.sort(students, Comparator.comparing(Student::getAge));

// 점수순
Arrays.sort(students, Comparator.comparing(Student::getScore));

// 이름순
Arrays.sort(students, Comparator.comparing(Student::getName));

// 내림차순
Arrays.sort(students, Comparator.comparing(Student::getAge).reversed());

// 복합 정렬: 1차 나이, 2차 이름
Arrays.sort(students, Comparator
    .comparing(Student::getAge)
    .thenComparing(Student::getName)
);

// null 처리
Arrays.sort(students, Comparator
    .comparing(Student::getName, Comparator.nullsFirst(String::compareTo))
);

Comparable vs Comparator

구분ComparableComparator
위치클래스 내부클래스 외부
메서드compareTo(T o)compare(T o1, T o2)
정렬 기준1개 (기본)여러 개 가능
사용Arrays.sort(arr)Arrays.sort(arr, comparator)
클래스 수정필요불필요
유연성낮음높음

언제 사용하나?

Comparable 사용:

// 명확한 "자연스러운 순서"가 있는 경우
Integer:  1 < 2 < 3 (숫자 크기)
String:   "A" < "B" < "C" (사전순)

// 예: 학생은 "학번순"이 자연스러운 순서
public class Student implements Comparable<Student> {
    private int studentId;
    
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.studentId, other.studentId);
    }
}

Comparator 사용:

// 다양한 정렬 기준이 필요한 경우
학생: 이름순, 나이순, 점수순, 학과순

// 예: 상황에 따라 다르게 정렬
Arrays.sort(students, Comparator.comparing(Student::getName));      // 출석부
Arrays.sort(students, Comparator.comparing(Student::getScore).reversed()); // 성적표
Arrays.sort(students, Comparator.comparing(Student::getAge));        // 생일 리스트

실전 예제

예제 1: 다중 조건 정렬

// 1차: 반 오름차순, 2차: 점수 내림차순, 3차: 이름 오름차순
students.sort(Comparator
    .comparing(Student::getClassNumber)
    .thenComparing(Student::getScore, Comparator.reverseOrder())
    .thenComparing(Student::getName)
);

예제 2: Map 정렬

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 85);
scores.put("Bob", 92);
scores.put("Charlie", 78);

// Value 기준 정렬
List<Map.Entry<String, Integer>> entries = new ArrayList<>(scores.entrySet());
entries.sort(Map.Entry.comparingByValue());
// 출력: [Charlie=78, Alice=85, Bob=92]

// Value 내림차순, 같으면 Key 오름차순
entries.sort(Map.Entry.<String, Integer>comparingByValue().reversed()
    .thenComparing(Map.Entry.comparingByKey()));

예제 3: 커스텀 정렬

// 짝수 먼저, 홀수 나중에, 각각 오름차순
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);

numbers.sort((a, b) -> {
    boolean aEven = a % 2 == 0;
    boolean bEven = b % 2 == 0;
    
    if (aEven && !bEven) return -1;
    if (!aEven && bEven) return 1;
    return Integer.compare(a, b);
});

System.out.println(numbers);
// 출력: [2, 4, 6, 8, 1, 3, 5, 7, 9]

주의사항

⚠️ Integer Overflow

// ❌ 위험한 코드
@Override
public int compareTo(Student other) {
    return this.age - other.age;  // Overflow 가능!
}

// ✅ 안전한 코드
@Override
public int compareTo(Student other) {
    return Integer.compare(this.age, other.age);
}

⚠️ NullPointerException

// ❌ 위험한 코드
Arrays.sort(students, Comparator.comparing(Student::getName));
// name이 null이면 NPE!

// ✅ 안전한 코드
Arrays.sort(students, Comparator.comparing(
    Student::getName, 
    Comparator.nullsFirst(String::compareTo)
));

9. 정렬 최적화 팁

Tip 1: 정렬 횟수 최소화

// 나쁨: 매번 정렬
for (int i = 0; i < 1000; i++) {
    list.add(newItem);
    Collections.sort(list);  // O(n log n) × 1000
}

// 좋음: 한 번만 정렬
for (int i = 0; i < 1000; i++) {
    list.add(newItem);
}
Collections.sort(list);  // O(n log n) × 1

Tip 2: Primitive vs Object

// 안정성 불필요 → Primitive (더 빠름)
int[] scores = {85, 92, 78};
Arrays.sort(scores);

// 안정성 필요 → Object
Integer[] scores = {85, 92, 78};
Arrays.sort(scores);

핵심 요약

정렬 알고리즘

✅ O(n log n) 알고리즘: Merge Sort, Quick Sort, Heap Sort, Tim Sort
✅ 안정 정렬: Merge Sort, Tim Sort, Insertion Sort
✅ 메모리 효율: Heap Sort (O(1)), Quick Sort (O(log n))
✅ 실제 데이터 최적: Tim Sort (부분 정렬 활용)

Java 정렬

✅ Java Primitive: Dual-Pivot Quick Sort (불안정, 빠름)
✅ Java Object: Tim Sort (안정, 실제 데이터 최적)
✅ 선택 기준: 데이터 크기, 상태, 안정성 요구사항, 메모리 제약

Comparator & Comparable

✅ Comparable: 클래스 내부 기본 정렬 기준 (1개)
✅ Comparator: 클래스 외부 다양한 정렬 기준 (여러 개)
✅ 리턴값 규칙: 음수(앞), 0(같음), 양수(뒤)
✅ 권장: Integer.compare() (Overflow 방지), nullsFirst/Last (NPE 방지)
✅ 메서드 체인: comparing().thenComparing().reversed() 등등

최적화

✅ 정렬 횟수 최소화
✅ 부분 정렬 활용
✅ Primitive 타입 우선 (안정성 불필요 시)
✅ Comparator 재사용

profile
devK08
안녕하세요. 개발자 지망 고등학생입니다.
이전 포스트

Hashing

다음 포스트

Compare And Swap (CAS) 개념 정리

0개의 댓글