09강: 정렬 알고리즘

이 강의에서 배우는 것

• 1버블·삽입·병합·퀵·계수 정렬의 원리와 시간/공간 복잡도를 설명할 수 있다.
• 2각 정렬의 **안정성(stable)** 과 **제자리 정렬(in-place)** 여부를 판별한다.
• 3주어진 문제 조건(n 크기, 데이터 범위, 안정성 요구)에 맞는 정렬을 선택한다.

개요

왜 정렬을 직접 구현하는가?

코딩 테스트에서 `sorted()` 하나면 끝나는 일이 많지만, 면접과 일부 문제는 정렬 알고리즘의 **작동 원리**와 **트레이드오프**를 직접 설명하거나 구현할 것을 요구합니다.

• **Bubble/Insertion**: 소규모 데이터, 거의 정렬된 데이터에 강점
• **Merge Sort**: 안정 정렬, 연결 리스트, 외부 정렬
• **Quick Sort**: 평균 최속, 캐시 효율 우수
• **Counting/Radix**: 비교 없이 O(n+k)

직접 구현해 보아야 "언제 어떤 정렬을 선택할까"를 몸으로 이해할 수 있습니다.

핵심 개념

시간 / 공간 복잡도 비교표

안정 정렬 (Stable Sort)

같은 키 값을 가진 원소들의 **상대적 순서**가 정렬 후에도 유지되는지 여부.

입력: [(A,2), (B,1), (C,2)]
안정 정렬 후: [(B,1), (A,2), (C,2)]  ← A가 C보다 앞 (원래 순서 유지)
불안정 정렬: [(B,1), (C,2), (A,2)]   ← 순서 보장 없음

Merge Sort 동작 도식

[5, 2, 8, 1, 9, 3]
        ↓ 분할
   [5, 2, 8]    [1, 9, 3]
      ↓              ↓
  [5,2] [8]     [1,9] [3]
    ↓               ↓
 [5][2] [8]    [1][9] [3]
    ↓ 병합          ↓ 병합
  [2,5]  [8]   [1,9]  [3]
      ↓              ↓
   [2,5,8]       [1,3,9]
          ↓ 최종 병합
      [1,2,3,5,8,9]

Quick Sort 분할 예시

피벗: 5
[3, 8, 5, 1, 9, 2, 7]
 ↓
[3, 1, 2] | [5] | [8, 9, 7]
    ↓                ↓
 [1,2,3]          [7,8,9]
          ↓
    [1,2,3,5,7,8,9]

예제로 보기

자주 하는 실수 5가지

1. **퀵 정렬 피벗을 항상 맨 앞/뒤 원소로 고정** - 이미 정렬된 배열에서 O(n²) 최악 케이스 발생 - 해결: 랜덤 피벗(`random.randint`) 또는 median-of-three 사용
2. **안정 정렬이 필요한 문제에 불안정 정렬 사용** - 다중 키 정렬(예: 이름 → 점수 순)에서 순서가 틀려짐 - 해결: `sorted()` (Timsort, 안정) 또는 Merge Sort 사용
3. **Counting Sort에서 값 범위 k를 배열 길이 n으로 착각** - 값 범위가 매우 클 때 메모리 초과 - 해결: k ≤ 10⁶ 정도일 때만 사용
4. **In-place Quick Sort에서 인덱스 범위 착오** - `left <= right` 와 `left < right` 구분 실수 - 단위 테스트: 길이 0, 1, 2 배열 먼저 검증
5. **Merge Sort 보조 배열을 매 재귀마다 새로 할당** - O(n log n) 공간이 돼 버림 - 해결: 전역 혹은 상위 레벨에서 한 번 할당

정리

직접 해 보기

1. 길이 10인 배열을 버블 정렬로 정렬하면서 **교환 횟수**를 세어 보세요.
2. 같은 배열을 삽입 정렬로 정렬하면서 **이동 횟수**를 세어 보세요.
3. 병합 정렬 코드에서 `merge` 함수가 호출되는 횟수를 세어 보세요.
4. 퀵 정렬에서 피벗을 항상 첫 번째 원소로 고정하면 `[1,2,3,4,5]` 입력 시 몇 번 비교가 일어나는지 계산해 보세요.

과제

`homework/README.md` 참조