14. 정렬 안정성 (Sort Stability) — 동일 키 순서 유지

핵심 인사이트 (3줄 요약)

1. 본질: 안정 정렬(Stable Sort)은 동일한 키를 가진 원소들의 상대적 순서를 정렬 전후로 보존하는 성질이며, 이는 기능적 정확성이 아니라 데이터 의미론의 문제다.
2. 가치: 다중 기준 정렬(성 → 이름 순), 데이터베이스 조인 후 정렬, 기수 정렬의 올바른 동작에 있어 안정성이 결과의 정확성을 보장하는 핵심 조건이다.
3. 판단 포인트: 키 외 부가 정보가 있는 레코드를 정렬할 때는 안정 정렬을 선택해야 하며, 불안정 정렬 사용 시 다중 키 정렬 결과가 의도와 달라질 수 있다.

Ⅰ. 개요 및 필요성

정렬 알고리즘을 평가할 때 속도만큼 중요한 속성이 **안정성 (Stability)**이다. 이는 동일한 정렬 키를 가진 원소들이 정렬 후에도 입력 순서를 유지하는가를 의미한다.

안정/불안정 정렬 분류

📢 섹션 요약 비유: 안정 정렬은 번호표를 나눠준 줄 세우기다. 같은 키를 가진 사람들은 번호표 순서대로 서 있게 되어, 나중에 누가 먼저 왔는지 알 수 있다. 불안정 정렬은 번호표 없이 키 순으로만 줄 세우기다.

Ⅱ. 아키텍처 및 핵심 원리

안정성 차이 ASCII 다이어그램

입력 레코드: [(Bob, 3등급), (Alice, 3등급), (Charlie, 1등급)]
          (이름, 성적 등급)  정렬 기준: 성적 등급

── 안정 정렬 결과 ─────────────────────────────────
입력 인덱스 순서 유지:
[(Charlie, 1등급), (Bob, 3등급), (Alice, 3등급)]
                      ↑ Bob이 Alice보다 먼저 → 입력 순서 보존 ✅

── 불안정 정렬 결과 ───────────────────────────────
임의 순서 가능:
[(Charlie, 1등급), (Alice, 3등급), (Bob, 3등급)]
                      ↑ Alice가 Bob보다 먼저 → 순서 역전 ⚠️
  또는
[(Charlie, 1등급), (Bob, 3등급), (Alice, 3등급)]
  → 운 좋게 맞을 수도 있지만 보장 없음

왜 불안정 정렬이 발생하나? (선택 정렬 예시)

입력: [B₁, A, B₂]  (B₁, B₂는 동일 키 B)

선택 정렬 1단계:
최솟값 A를 찾아 B₁과 교환:
  [A, B₁, B₂] → [A, B₂, B₁] ← B₁, B₂ 순서 역전!
     ↑ B₂가 B₁보다 앞으로

선택 정렬은 교환(Swap) 연산이 키 외 순서를 파괴함 → 불안정

안정 정렬이 보장되는 이유 (삽입 정렬 예시)

입력: [B₁, A, B₂]

삽입 정렬:
  A를 앞으로 이동 시 B₁을 만나면 이미 B₁ < A이므로 중단
  → B₁과 B₂의 상대 위치는 절대 바뀌지 않음 ✅
  
원칙: "같은 키는 더 앞에 있는 원소를 이기지 못한다"

다중 키 정렬에서 안정성의 중요성

📢 섹션 요약 비유: 다중 키 정렬의 안정성은 선착순 + 점수순 대기열과 같다. 먼저 점수순으로 줄을 세웠을 때, 같은 점수면 먼저 온 사람이 앞에 있어야 한다. 이를 보장하지 않으면 선착순 의미가 사라진다.

Ⅲ. 비교 및 연결

정렬 알고리즘별 안정성/복잡도 종합 비교

불안정 정렬을 안정화하는 방법

방법 1: 원래 인덱스를 보조 키로 추가
  (key, index) 쌍으로 정렬 → 같은 key는 index 순
  공간: O(n) 추가, 시간: 정렬 복잡도 유지

방법 2: 안정 래퍼(Stable Wrapper) 패턴
  Python: sorted(arr, key=lambda x: (x.key, original_index))

📢 섹션 요약 비유: 안정/불안정 정렬의 차이는 단체 사진에서 같은 키의 사람들 순서를 정하는 방법과 같다. 안정 정렬은 "이미 서 있던 순서대로", 불안정 정렬은 "사진사 마음대로"다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1 — 전자상거래 상품 정렬: 먼저 카테고리순, 같은 카테고리 내 가격 낮은 순
→ 가격으로 먼저 정렬(안정 정렬) → 카테고리로 정렬
→ 같은 카테고리 내 가격 순서 보존 ✅

시나리오 2 — 데이터베이스 ORDER BY 다중 컬럼: ORDER BY grade ASC, name ASC
→ name으로 먼저 안정 정렬 → grade로 안정 정렬
→ 최종: grade 순 정렬, 같은 grade는 name 순 ✅

시나리오 3 — 기수 정렬 내부: 십의 자리 정렬 후 백의 자리 정렬 시
→ 반드시 안정 정렬이어야 십의 자리 결과가 보존됨

기술사 선택 가이드

┌──────────────────────────────────────────────────────┐
│  정렬 알고리즘 선택 의사결정 트리                     │
│                                                      │
│  동일 키 원소의 순서가 중요한가?                     │
│    │ Yes → 안정 정렬 필수                            │
│    │       → 병합 정렬, Timsort, 삽입 정렬 선택      │
│    │ No  → 불안정 정렬도 가능                        │
│             → Introsort, 힙 정렬 검토                │
│                                                      │
│  다중 키 정렬인가?                                   │
│    → 반드시 안정 정렬 사용할 것                      │
└──────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 정렬 안정성은 법정 증거 보전과 같다. 원본 증거(입력 순서)가 정렬 과정에서 훼손되면, 법정(다중 키 정렬, 기수 정렬)에서 판결이 잘못된다.

Ⅴ. 기대효과 및 결론

정렬 안정성은 단순한 구현 세부사항이 아니라 데이터의 의미론적 정확성을 보장하는 알고리즘 속성이다. 실무에서 다중 키 정렬, 데이터베이스 처리, 알고리즘 조합(기수 정렬)에서 안정성 여부는 결과 정확성을 직접 결정한다.

효과 정리

📢 섹션 요약 비유: 안정 정렬은 줄 서기 규칙이 명확한 공공기관과 같다. "같은 번호표라면 먼저 온 사람이 먼저"라는 원칙이 있어야 모든 사람이 시스템을 신뢰할 수 있다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[정렬 안정성 (Sort Stability) — 동일 키를 가진 요소의 원본 순서 보존]
    │
    ▼
[안정 정렬 — 버블·삽입·병합 정렬 (Stable Sort), 원본 순서 유지 보장]
    │
    ▼
[불안정 정렬 — 퀵·힙·선택 정렬 (Unstable Sort), 원본 순서 미보장]
    │
    ▼
[다중 키 정렬 — 우선순위 낮은 키 먼저 안정 정렬로 복합 키 정렬 구현]
    │
    ▼
[Tim Sort — 안정 정렬 + 실세계 데이터 최적화, Python·Java 기본 정렬]

이 흐름은 안정성의 개념에서 안정/불안정 정렬의 트레이드오프를 거쳐, 다중 키 정렬 실무 응용과 최신 Tim Sort로 이어지는 정렬 안정성의 실용적 발전 과정을 보여준다.

👶 어린이를 위한 3줄 비유 설명

🎭 같은 반 짝꿍 줄 세우기: 키가 같은 친구들이 여럿이면, 먼저 온 순서대로 줄 세우는 게 안정 정렬이에요. 불안정 정렬은 같은 키면 누가 앞에 서든 상관없다고 해요.
🃏 같은 숫자 카드 정리: 하트 5와 다이아 5를 순서대로 정리할 때, 안정 정렬은 원래 카드 순서를 기억해서 같은 숫자를 정렬해요.
📋 성적표 다중 정렬: 먼저 이름순 정렬 후 점수순으로 재정렬할 때, 같은 점수면 이름 순서가 그대로 남아 있어야 제대로 된 성적표가 돼요!