실무에서 정렬 알고리즘을 직접 구현할 일은 드뭅니다. 대신 언어와 라이브러리가 어떤 정렬을 쓰는지, 그 정렬이 안정적인지, 비교 함수를 어떻게 넘겨야 안전한지를 아는 것이 중요합니다. 이 장에서는 주요 언어의 내장 정렬과 자주 겪는 함정, 그리고 정렬 대신 쓸 수 있는 도구를 정리합니다.
언어별 내장 정렬
Python의 Timsort는 입력에서 이미 정렬된 구간(run)을 찾아내고, 짧은 구간은 이진 삽입 정렬로 늘린 뒤, 구간들을 병합합니다. 한쪽에서 연달아 원소가 나오면 지수 탐색으로 건너뛰는 갤로핑(galloping) 모드도 있습니다. 그래서 이미 정렬되었거나 거의 정렬된 데이터, 정렬된 목록 두 개를 이어 붙인 데이터에서 매우 빠릅니다. CPython 3.11부터는 구간을 병합하는 순서를 정하는 규칙이 Powersort 방식으로 바뀌었지만 안정성과 O(n log n) 최악 보장은 그대로입니다. Java는 객체 정렬에 Python의 Timsort를 옮겨 온 구현을 씁니다.
C++ 표준은 std::sort의 알고리즘을 정하지 않고 C++11부터 O(n log n) 비교 횟수만 요구합니다. libstdc++ 같은 주요 구현은 인트로소트(introsort)를 씁니다. 퀵 정렬로 시작하되 재귀가 2 log n 정도로 깊어지면 힙 정렬로 바꾸어 최악을 막고, 작은 구간은 삽입 정렬로 마무리합니다. 안정성이 필요하면 std::stable_sort를 써야 합니다.
정렬하지 않아도 되는 경우
전체를 정렬하지 않고 일부만 필요하다면 더 싼 도구가 있습니다.
import heapq
scores = [72, 95, 88, 61, 99, 85, 90, 77]
print(heapq.nlargest(3, scores)) # [99, 95, 90] O(n log k)
print(heapq.nsmallest(2, scores)) # [61, 72]
import bisect
ranked = sorted(scores)
bisect.insort(ranked, 93) # 정렬 상태를 유지하며 삽입
print(ranked[bisect.bisect_left(ranked, 90):]) # 90 이상: [90, 93, 95, 99]
C++에서는 std::partial_sort가 앞의 k개만 정렬하고, std::nth_element는 k번째 원소를 제자리에 두고 양쪽을 나누기만 합니다(평균 O(n)). 중앙값이나 백분위수를 구할 때 유용합니다.
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{72, 95, 88, 61, 99, 85, 90, 77};
std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
std::cout << "median-ish: " << v[v.size() / 2] << '\n'; // 88
std::partial_sort(v.begin(), v.begin() + 3, v.end(), std::greater<int>());
std::cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n'; // 99 95 90
}
데이터베이스에서는 ORDER BY 열에 인덱스가 있으면 정렬 없이 인덱스 순서로 읽고, 메모리에 다 들어가지 않는 결과는 조각을 정렬해 디스크에 쓴 뒤 병합하는 외부 정렬을 씁니다. 대용량 로그를 정렬하는 유닉스 sort 명령도 같은 원리입니다.
자주 겪는 함정
- JavaScript의 기본 정렬은 원소를 문자열로 바꾸어 비교합니다.
[10, 9, 1].sort()는 [1, 10, 9]이므로 숫자는 반드시 (a, b) => a - b를 넘깁니다. - 비교 함수가 일관되지 않으면(추이성이 없거나 무작위 값을 돌려주면) 결과가 엉망이 되거나, Java에서는
IllegalArgumentException: Comparison method violates its general contract!가 날 수 있습니다. - Java에서
(a, b) -> a - b는 큰 값에서 정수 오버플로가 납니다. Integer.compare나 Comparator.comparingInt를 씁니다. NaN은 어떤 값과도 크기 비교가 거짓이라 정렬 결과를 망가뜨립니다. 미리 걸러 내거나 키에서 따로 처리합니다.- 사람이 읽는 문자열 정렬은 코드 포인트 순서와 다릅니다. 대소문자, 악센트, 언어별 규칙이 필요하면
Intl.Collator나 ICU 같은 로캘 인식 비교를 씁니다.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Ranking {
record Player(String name, int score) {}
public static void main(String[] args) {
List<Player> players = new ArrayList<>(List.of(
new Player("lee", 90), new Player("kim", 95), new Player("park", 90)));
players.sort(Comparator.comparingInt(Player::score).reversed()
.thenComparing(Player::name));
System.out.println(players); // kim 95, lee 90, park 90 순서
}
}
const nums = [10, 9, 1];
console.log([...nums].sort()); // [1, 10, 9] 문자열 비교
console.log([...nums].sort((a, b) => a - b)); // [1, 9, 10]
const names = ["Émile", "zoe", "Adam"];
console.log([...names].sort(new Intl.Collator("fr").compare)); // ["Adam", "Émile", "zoe"]
더 읽을거리
정리
- 내장 정렬의 알고리즘과 안정성을 알고 쓰면 대부분의 실무 요구를 충족합니다.
- 상위 k개, 중앙값, 정렬 상태 유지에는 전체 정렬보다 힙, 선택, 이진 탐색 도구가 적합합니다.
- 비교 함수의 일관성, 숫자와 문자열 비교의 차이,
NaN, 로캘 규칙이 가장 흔한 버그 원인입니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.