[Algorithm] 정렬 알고리즘 심화 분석: O(n²)부터 Timsort까지

ALGORITHM NOTE

정렬 알고리즘 심화 분석: O(n²)부터 Timsort까지

목차

• 1. O(n²) 정렬 3종 비교 (버블/선택/삽입)
• 2. 퀵 정렬(Quick Sort): 성능 원리와 최악의 조건
• 3. 병합 정렬(Merge Sort)과 안정 정렬(Stable Sort)
• 4. Java Arrays.sort()와 Timsort의 비밀
• 5. 추가 개념: Swap Flag 및 용어 정리

01. 버블 / 선택 / 삽입 - O(n²)의 성능 차이

셋 다 시간 복잡도는 O(n^2)이지만, 실제 동작 방식에 따라 성능 차이가 발생합니다.

• 선택 정렬 (Selection Sort): 매 라운드 최솟값을 찾아 맨 앞과 교환합니다. 비교 횟수는 항상 n(n-1)/2로 고정이며, 이미 정렬된 상태라도 성능이 개선되지 않아 실용성이 낮습니다.
• 버블 정렬 (Bubble Sort): 인접한 두 원소를 비교하며 교환합니다. 교환(swap) 작업이 빈번하게 일어나고 캐시 효율이 나빠 실제 성능이 가장 떨어지는 경우가 많습니다.
• 삽입 정렬 (Insertion Sort): 정렬된 부분의 적절한 위치에 원소를 삽입합니다. 데이터가 거의 정렬된 상태라면 O(n)에 수렴하는 강력한 특징이 있어 Timsort의 핵심 서브루틴으로 사용됩니다.

02. 퀵 정렬 - 평균 O(n log n), 최악 O(n^2)

분할 정복의 원리

피벗(Pivot)을 기준으로 배열을 반씩 나눕니다. 이상적으로 절반씩 나뉜다면 재귀 깊이는 log n이 되고, 각 단계에서 n번 비교하므로 O(n log n)이 됩니다.

최악의 상황 (O(n^2))

이미 정렬된 배열에서 첫 번째 원소를 피벗으로 선택하면, 분할이 [1개] + [n-1개]로만 이루어져 재귀 깊이가 n까지 늘어납니다.

[1, 2, 3, 4, 5] → pivot:1 → [] + [2,3,4,5]
[2, 3, 4, 5]    → pivot:2 → [] + [3,4,5] (재귀 n번 발생)

실무에서의 대응

피벗을 랜덤하게 정하거나 첫/중간/끝 값 중 중간값을 피벗으로 쓰는 Median-of-Three 기법을 사용합니다. Java의 Dual-Pivot Quicksort는 피벗 2개를 사용하여 성능을 높이고, 재귀가 너무 깊어지면 힙 정렬로 전환하는 하이브리드 방식을 취합니다.

 

03. 병합 정렬이 '안정 정렬'인 이유

병합 정렬은 원소가 하나가 될 때까지 쪼갠 후, 다시 합치면서 정렬하는 방식입니다.

💡 핵심: 안정성(Stability)의 결정타

병합(Merge) 시 동일한 값을 만나면 반드시 왼쪽 배열의 원소를 먼저 결과에 담습니다.

if (arr[i] <= arr[j]) {
    temp[k++] = arr[i++]; // 등호(=)가 순서를 유지함
}

만약 <= 대신 <를 사용하면 동일 값일 때 오른쪽 배열의 원소가 먼저 들어가 순서가 뒤집히게(Unstable) 됩니다.

 

04. Java Arrays.sort()와 Timsort

정렬 대상	사용 알고리즘
Primitive Type (int[], double[]...)	Dual-Pivot Quicksort (속도 우선)
Object Type (String[], Custom Class...)	Timsort (안정성 보장)

왜 객체 정렬에는 Timsort인가?

객체 정렬은 안정 정렬이 필수적입니다. Timsort는 병합 정렬 + 삽입 정렬의 하이브리드 알고리즘으로, 실세계 데이터의 '부분 정렬 상태'를 최대한 활용하여 최선의 경우 O(n), 최악의 경우에도 O(n log n)을 보장합니다.

 

05. 심화 개념 및 용어 정리

버블 정렬의 최적화: Swap Flag

for (int i = 0; i < n - 1; i++) {
    boolean swapped = false; // swap flag
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            swap(arr, j, j + 1);
            swapped = true;
        }
    }
    if (!swapped) break; // 교환 없으면 조기 종료 (최선 O(n))
}

Timsort란?

Python 개발자 Tim Peters가 고안한 하이브리드 정렬. 이론적 최적을 넘어 실제 데이터 환경에서 최상의 퍼포먼스를 내도록 설계됨.

서브루틴(Subroutine)이란?

특정 작업을 수행하기 위해 호출되는 부품 함수. Timsort가 각 구간을 정렬할 때 사용하는 '삽입 정렬'이 바로 서브루틴의 예시.

Last Sync: 2026-04-29 | Algorithm Study Archive