정렬 14종 경주 — 같은 배열, 다른 연산 수
같은 무작위 배열을 14종 정렬이 실제로 정렬하며 비교+이동 연산을 실측하고, 그 역수를 속도로 삼은 레인 경주로 완주 순서를 보여준다.
1 / 14같은 무작위 배열(16개)을 14종이 동시에 정렬합니다. 진행 속도 = 연산(비교+이동) 수의 역수 — 전부 실측입니다. 준비, 출발!
버블O(n²)179연산
칵테일O(n²)164연산
선택O(n²)133연산
삽입O(n²)146연산
놈O(n²)193연산
셸O(n log² n)174연산
빗질O(n²/2ᵖ)115연산
병합O(n log n)113연산
퀵O(n log n)78연산
힙O(n log n)121연산
팀(런+병합)O(n log n)105연산
계수O(n+k)32연산
기수O(d·(n+k))34연산
버킷O(n+k)65연산
단계 목록 · 키보드 ←/→ 이동, Space 재생
경주의 결말은 세 계열로 갈린다 — 값의 범위를 전제로 비교 자체를 안 하는 선형 계열(계수·기수·버킷), 분할·병합의 O(n log n) 계열, 이웃만 보는 O(n²) 계열. 그리고 실전은 이들의 혼합(팀솔트)을 쓴다.
왜 헷갈리는가
"계수 정렬이 제일 빠르네, 항상 이걸 쓰면 되겠다"가 함정이다 — 선형 계열은 '값이 좁은 정수 범위'라는 전제를 산 것이라 실수·문자열·넓은 범위에서 무너진다. 비교만으로 정렬하는 한 O(n log n)이 수학적 하한이다.
경주가 보여주는 것
n=16에서도 버블과 계수의 연산 수는 수 배 차이다 — n이 만이면 경주가 되지 않는다. O(n²) 계열(버블·칵테일·선택·삽입·놈)은 이웃 교환의 변주들이고, O(n log n) 계열(병합·퀵·힙·팀)은 '반씩 나눠 정복'의 변주들이며, 선형 계열은 값 자체를 주소로 쓴다.
그래도 O(n²)가 사는 곳이 있다: 삽입 정렬은 '거의 정렬된' 배열에서 O(n)에 가깝고 상수가 작다 — 그래서 팀솔트(파이썬·자바 표준)가 작은 런을 삽입으로 다듬고 병합하며, C++의 인트로솔트는 퀵으로 시작해 재귀가 깊어지면 힙으로 도망간다.
고를 때 묻는 것
정렬을 직접 고르는 드문 순간의 체크리스트.
- 안정성(같은 키의 순서 보존)이 필요한가 — 병합·팀·계수는 안정, 퀵·힙·선택은 불안정. '이름으로 정렬 후 부서로 정렬'이 성립하려면 안정 정렬.
- 메모리가 조이는가 — 힙·퀵은 제자리(O(1)~O(log n)), 병합·계수는 추가 공간 O(n).
- 값의 분포를 아는가 — 좁은 정수(나이·점수)면 계수/기수가 압살한다.
- 최악 보장이 필요한가 — 퀵은 평균 최강·최악 O(n²), 힙·병합은 최악도 O(n log n).
- 현실 답: 언어 표준 sort()를 쓴다 — 그 안이 이미 이 경주의 우승자들을 조합해 놓았다.
기억할 것
- 세 계열: 이웃 교환 O(n²) · 분할 정복 O(n log n) · 값=주소 O(n+k).
- 비교 정렬의 하한은 O(n log n) — 그 아래는 전제(좁은 값 범위)를 산 것이다.
- 삽입 정렬은 '거의 정렬됨'에서 부활한다 — 하이브리드의 재료.
- 실전은 팀솔트·인트로솔트 — 표준 라이브러리가 이미 최적 조합이다.