topic★★★★★난이도 · 약 20분
정렬 알고리즘 — 버블·선택·퀵·머지 + 안정성
O(n²) 초보 3종 vs O(n log n) 실전 2종, 그리고 '안정 정렬'이라는 숨은 함정.
#정렬#Timsort#퀵정렬#머지정렬#안정정렬
왜 배우는가
"리스트 정렬해줘"가 Claude에게 가장 흔한 요청. 직접 구현할 일은 없지만 `Array.sort()`가 내부에서 뭘 쓰는지, '안정(stable)'이 왜 중요한지 알면 실수 안 한다.
실전에서는 거의 항상 언어 내장 `.sort()`를 쓴다. 하지만 비교 함수·안정성·Big O를 알아야 이상한 순서 결과 같은 버그를 피한다.
| 알고리즘 | 평균 | 최악 | 공간 | 안정? | 실무 |
|---|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | ✅ | 교육용만 |
| 선택 정렬 | O(n²) | O(n²) | O(1) | ❌ | 교육용만 |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | ✅ | 작은 n에서 빠름 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | ❌ | V8 기본(과거) |
| 머지 정렬 | O(n log n) | O(n log n) | O(n) | ✅ | 안정성 필요할 때 |
| Timsort | O(n log n) | O(n log n) | O(n) | ✅ | JS·Python·Java 표준 |
javascript
// ━━━ 내장 sort 사용법 ━━━
[3, 1, 10, 2].sort(); // [1, 10, 2, 3] ← 문자열 비교! 주의
[3, 1, 10, 2].sort((a, b) => a - b); // [1, 2, 3, 10] ← 숫자 정렬
// 객체 정렬
users.sort((a, b) => a.age - b.age); // 나이 오름
users.sort((a, b) => b.createdAt - a.createdAt); // 최신 먼저
// 다중 키 (나이 오름 → 같으면 이름 오름)
users.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name));
// ━━━ 안정 정렬의 중요성 ━━━
// 이미 "가입일 오름차순" 정렬된 배열을 "나이"로 재정렬
// → 안정 정렬이면 같은 나이 내에선 가입일 순서 유지
// → 불안정 정렬은 뒤섞임
// 다행히 2019년 이후 JS/Python/Java sort는 **안정**
// 과거 V8은 불안정(QuickSort 변형)이었음 — 구형 브라우저 호환 주의`.sort()`에 비교 함수 없이 숫자 배열을 넘기면 문자열로 비교하는 고전 함정. Claude 생성 코드에서도 가끔 나오므로 주의.
Timsort는 머지 정렬 + 삽입 정렬 하이브리드. 실세계 데이터가 "부분적으로 이미 정렬"돼 있는 특성을 활용해 빠르다. 2002년 Python 도입, 이후 JS·Java 표준. 대부분의 바이브코더 코드는 실제로 Timsort 위에서 돈다.
퀵 정렬 최악 O(n²) 함정. 이미 정렬된 배열이나 같은 값이 많은 경우 피벗 선택 실패로 O(n²). 악의적 입력으로 서버를 느리게 만드는 공격(slowloris 변형)도 있었음. Timsort가 표준인 이유.
실기 드릴 2문항
edit실기 드릴 · 단답형
JS·Python·Java의 표준 정렬이 쓰는 하이브리드 알고리즘 이름은?
check_circle실기 드릴 · OX
`[3,1,10,2].sort()`의 결과는 `[1,2,3,10]`이다.