Sorting

정렬 알고리즘 개요

코딩 테스트에서 다루는 주요 정렬 알고리즘 8가지를 여러 기준으로 분류하여 정리한다.

---

문서 목록

파일	알고리즘
bubble_sort.md	버블 정렬
selection_sort.md	선택 정렬
insertion_sort.md	삽입 정렬
merge_sort.md	병합 정렬
quick_sort.md	퀵 정렬
heap_sort.md	힙 정렬
counting_sort.md	계수 정렬
radix_sort.md	기수 정렬

---

분류 1 — 비교 기반 vs 비비교 기반

정렬 알고리즘을 가장 근본적으로 나누는 기준이다.

비교 기반 정렬(Comparison Sort) 은 두 원소를 >, < 등의 연산으로 비교하여 순서를 결정한다. 정보 이론에 의해 최악의 경우 Ω(n log n) 비교가 반드시 필요하다는 것이 수학적으로 증명되어 있다.

비비교 기반 정렬(Non-comparison Sort) 은 원소의 값 자체(자릿수, 빈도)를 활용하여 비교 없이 정렬한다. 이론적 하한을 우회해 O(n) 에 근접할 수 있지만, 적용 가능한 데이터 조건이 존재한다.

구분	알고리즘	이론적 하한
비교 기반	버블, 선택, 삽입, 병합, 퀵, 힙	Ω(n log n)
비비교 기반	계수, 기수	O(n) 가능

---

분류 2 — 알고리즘 패러다임

어떤 전략으로 정렬 문제를 해결하느냐에 따라 구분한다.

단순 반복 (Brute-force)

매 단계마다 인접 비교·교환 또는 최솟값 탐색을 반복한다. 구현이 단순하지만 O(n²)이다.

알고리즘	핵심 아이디어
버블 정렬	인접한 두 원소를 비교해 교환 반복
선택 정렬	미정렬 구간의 최솟값을 선택해 제자리에 배치
삽입 정렬	미정렬 원소를 정렬된 구간의 올바른 위치에 삽입

분할 정복 (Divide & Conquer)

문제를 작은 부분으로 나눠 재귀적으로 해결한다. O(n log n)이다.

알고리즘	핵심 아이디어
병합 정렬	반으로 나눠 각각 정렬 후 병합
퀵 정렬	피벗 기준으로 분할 후 각 부분 재귀 정렬

자료구조 활용 (Heap)

특수 자료구조의 성질을 이용하여 정렬한다.

알고리즘	핵심 아이디어
힙 정렬	최대 힙으로 구성 후 루트(최댓값)를 반복 추출

분포 기반 (Distribution)

원소의 값 분포를 활용해 비교 없이 정렬한다.

알고리즘	핵심 아이디어
계수 정렬	각 값의 등장 횟수를 기록해 순서대로 나열
기수 정렬	자릿수 단위로 반복 계수 정렬 적용

---

분류 3 — 시간 복잡도

복잡도	알고리즘	조건
O(n)	삽입 정렬	이미 정렬된 배열 (최선)
O(n)	계수 정렬, 기수 정렬	값 범위 k = O(n) 조건 하
O(n log n)	병합 정렬, 힙 정렬	항상 보장
O(n log n)	퀵 정렬	평균 (최악은 O(n²))
O(n²)	버블, 선택, 삽입	평균·최악

비교 기반 정렬에서 항상 O(n log n)을 보장하는 것은 병합 정렬과 힙 정렬뿐이다.
퀵 정렬은 평균적으로 가장 빠르지만 최악은 O(n²)이다.

---

분류 4 — 공간 복잡도 (제자리 정렬 여부)

구분	알고리즘	공간 복잡도
제자리 O(1)	버블, 선택, 삽입, 힙	O(1)
스택 O(log n)	퀵 (재귀 스택)	O(log n)
추가 배열 필요	병합	O(n)
카운트 배열 필요	계수	O(k)
출력 배열 필요	기수	O(n + k)

최악 O(n log n) + 공간 O(1) 을 동시에 만족하는 비교 기반 정렬은 힙 정렬뿐이다.

---

분류 5 — 안정성 (Stability)

동일한 키를 가진 원소들의 원래 상대적 순서가 정렬 후에도 유지되는지 여부.

다중 키 정렬(예: 이름으로 정렬된 결과를 나이로 다시 정렬)이나 기수 정렬의 서브루틴으로 사용할 때 안정성이 필수적으로 요구된다.

구분	알고리즘
안정 (Stable)	버블, 삽입, 병합, 계수, 기수
불안정 (Unstable)	선택, 퀵, 힙

---

분류 6 — 적응성 (Adaptivity)

입력 데이터가 이미 부분적으로 정렬되어 있을 때 더 빠르게 동작하는지 여부.

구분	알고리즘	이유
적응적 (Adaptive)	삽입, 버블 (조기 종료)	정렬된 구간은 비교만 하고 이동 없음
비적응적 (Non-adaptive)	선택, 힙, 병합, 퀵, 계수, 기수	입력 상태와 무관하게 동일한 연산 수행

Java의 Tim Sort(삽입 + 병합)가 실제 데이터에서 빠른 이유가 적응성 때문이다.

---

분류 7 — 적용 가능 조건

구분	알고리즘	조건
범용	버블, 선택, 삽입, 병합, 퀵, 힙	비교 가능한 모든 데이터
정수 한정	계수, 기수	정수 또는 정수로 매핑 가능한 값
범위 제한	계수	값의 범위 k가 충분히 작아야 함
자릿수 고정	기수	자릿수 d가 작아야 효율적

---

알고리즘 간 연결고리

개별 알고리즘을 넘어 서로 어떻게 연결되는지 이해하면 정렬을 더 깊이 파악할 수 있다.

역위(Inversion)와 정렬 성능

역위란 배열에서 i < j이지만 arr[i] > arr[j]인 쌍의 수다. 정렬이 완료된 상태의 역위 수는 0이며, 역위가 많을수록 정렬이 더 많은 작업을 필요로 한다.

알고리즘	역위와의 관계
버블 정렬	교환 횟수 = 역위의 수
삽입 정렬	총 이동(shift) 횟수 = 역위의 수. 역위가 적을수록 빠름 (적응성의 근거)
병합 정렬	병합 시 오른쪽 원소가 먼저 선택될 때마다 역위가 누적됨 → O(n log n)에 역위 총 개수 계산 가능

역위 수가 O(n)이면 삽입 정렬이 O(n)으로 동작한다. 역위 개수를 세는 문제(BOJ 1517)는 병합 정렬로 O(n log n)에 해결한다.

계수 정렬 → 기수 정렬

기수 정렬은 계수 정렬을 서브루틴으로 사용한다. 각 자릿수 단위의 정렬을 계수 정렬로 수행하며, 이때 계수 정렬이 반드시 안정 정렬이어야 낮은 자리의 정렬 결과가 보존된다.

기수 정렬
  └─ 1의 자리: 계수 정렬 (안정)
  └─ 10의 자리: 계수 정렬 (안정)
  └─ 100의 자리: 계수 정렬 (안정)
  ...

계수 정렬이 불안정하다면 자릿수를 올라갈수록 이전 정렬 결과가 깨져 최종 결과가 틀린다.

삽입 정렬 + 병합 정렬 → Tim Sort

Java의 Arrays.sort(Object[]), Python의 sorted()에 사용되는 Tim Sort는 두 알고리즘의 장점을 결합한다.

역할	알고리즘	이유
소규모 구간 정렬	삽입 정렬	n이 작을 때(≤32~64) 오버헤드가 적고, 부분 정렬 시 적응성 발휘
전체 병합	병합 정렬	안정 정렬 보장, 항상 O(n log n)

실제 데이터는 완전 무작위가 아닌 부분 정렬된 구간(run)이 많아, Tim Sort가 이를 적극 활용한다.

---

비교 기반 정렬의 하한: 왜 O(n log n)이 최선인가

비교 기반 정렬에서 어떤 알고리즘도 최악의 경우 Ω(n log n)번의 비교 를 피할 수 없다. 이는 수학적으로 증명된 사실이며, 직관적으로는 다음과 같이 이해할 수 있다.

결정 트리(Decision Tree) 모델

n개의 원소를 정렬하는 과정을 이진 결정 트리로 표현할 수 있다.

• 각 내부 노드: 두 원소를 비교하는 결정 (arr[i] < arr[j]?)
• 각 리프 노드: 하나의 가능한 정렬 결과 (순열)
• n개의 원소가 가질 수 있는 순열의 수: n!

트리의 리프 노드가 최소 n!개 이상 있어야 모든 입력 순서를 구별할 수 있다.

높이가 h인 이진 트리의 최대 리프 수 = 2^h

따라서: 2^h ≥ n!
→ h ≥ log₂(n!)
→ h ≥ Ω(n log n)   (스털링 근사: log(n!) ≈ n log n)

즉, 어떤 비교 기반 정렬도 최악의 경우 최소 Ω(n log n)번의 비교가 반드시 필요하다.

비비교 기반 정렬이 이를 우회하는 이유

계수·기수 정렬은 원소를 직접 비교하지 않고 값 자체를 배열 인덱스로 활용한다. 결정 트리 모델이 적용되지 않으므로 이 하한에 구속되지 않는다. 단, 그 대신 데이터가 정수이거나 범위가 제한되어야 한다는 조건이 필요하다.

---

종합 비교표

알고리즘	최선	평균	최악	공간	안정	적응	패러다임
버블 정렬	O(n)	O(n²)	O(n²)	O(1)	✅	✅	단순 반복
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	❌	❌	단순 반복
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)	✅	✅	단순 반복
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	❌	분할 정복
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(log n)	❌	❌	분할 정복
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	❌	❌	자료구조
계수 정렬	O(n + k)	O(n + k)	O(n + k)	O(k)	✅	❌	분포 기반
기수 정렬	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	✅	❌	분포 기반

---

선택 가이드

데이터가 정수이고 값의 범위가 작다 (k ≤ 10^6)
    └─→ 계수 정렬 / 기수 정렬

데이터가 거의 정렬되어 있다
    └─→ 삽입 정렬

안정 정렬이 필요하다 + 최악도 보장해야 한다
    └─→ 병합 정렬

메모리가 제한적이다 + 최악도 보장해야 한다
    └─→ 힙 정렬

일반적인 범용 정렬 (빠른 평균 성능)
    └─→ 퀵 정렬 (랜덤 피벗) 또는 Arrays.sort()

n이 작다 (n ≤ 1,000)
    └─→ 삽입 정렬 (구현 단순 + 오버헤드 적음)