정렬은 이미 만들어져 있습니다. 그래서 무엇이 보장되는지 확인하지 않고 씁니다.
숫자 배열을 정렬하면 숫자 순이 아닙니다
자바스크립트의 기본 정렬부터 확인하고 시작합니다.
[10, 9, 80, 7].sort();
// 결과: [10, 7, 80, 9]Array.prototype.sort()는 비교 함수를 주지 않으면 원소를 문자열로 변환한 뒤 UTF-16 코드 단위 순서로 비교합니다. "10"이 "9"보다 앞서므로 10, 7, 80, 9 순서가 나옵니다.
숫자 정렬에는 비교 함수가 필요합니다.
[10, 9, 80, 7].sort((a, b) => a - b);
// 결과: [7, 9, 10, 80]비교 함수는 음수를 반환하면 a를 앞에, 양수를 반환하면 b를 앞에 둡니다. 0이면 순서를 유지합니다. 두 원소가 같다고 판정되어 0이 반환됐을 때 원래 순서가 그대로 유지되는지가 안정 정렬의 문제이고, 다음 절에서 다룹니다.
안정 정렬은 순서를 잃지 않는 성질입니다
안정 정렬(stable sort) 은 비교했을 때 같다고 판정된 원소들의 원래 순서를 그대로 유지하는 정렬입니다.
말로만 보면 사소해 보입니다. 다중 기준 정렬에 들어가면 성격이 달라집니다.
주문 목록을 지역별로 묶되 각 지역 안에서는 최신순으로 보여줘야 한다고 해봅시다. 비교 함수 하나에 두 조건을 다 넣을 수도 있지만, 안정 정렬이 보장되면 두 번 나눠 정렬해도 됩니다.
// 안쪽 기준을 먼저, 바깥 기준을 나중에
orders.sort((a, b) => b.createdAt - a.createdAt); // 최신순
orders.sort((a, b) => a.region.localeCompare(b.region)); // 지역순두 번째 정렬에서 같은 지역끼리는 비교 결과가 0입니다. 안정 정렬이면 이들의 상대 순서, 즉 첫 번째 정렬로 맞춰둔 최신순이 그대로 남습니다.
안정성이 보장되지 않으면 이렇게 두 번 나눠 정렬하는 방법은 실패합니다. 지역은 맞게 묶이지만 안쪽 순서가 뒤섞입니다. 재현이 어렵고 원인을 찾기도 까다로운 버그가 됩니다.
ECMAScript 2019부터 Array.prototype.sort()는 안정 정렬로 규정되었습니다. 그 이전 사양에서는 안정성이 요구되지 않았고, 엔진마다 배열 길이에 따라 다른 알고리즘을 쓰는 경우가 있었습니다. 오래된 환경을 지원해야 한다면 이 부분을 확인해야 합니다.
비교 함수는 한 줄로도 됩니다
두 번 정렬하는 대신 비교 함수에 조건을 이어 붙일 수도 있습니다. 앞 기준이 같을 때만 다음 기준으로 넘어가는 구조입니다.
orders.sort((a, b) => {
const byRegion = a.region.localeCompare(b.region);
if (byRegion !== 0) return byRegion; // 지역이 다르면 여기서 결정
return b.createdAt - a.createdAt; // 같으면 최신순
});문자열 비교에 localeCompare를 쓴 이유는, 한글이나 악센트가 붙은 문자를 < 연산자로 비교하면 유니코드 기준 순서가 나와서 사람이 기대하는 사전 순과 어긋나기 때문입니다. 사용자에게 보이는 목록이라면 로케일을 반영하는 비교가 맞습니다.
세 가지 정렬의 성격
직접 구현할 일은 드물지만, 내장 정렬이 어떤 선택을 했는지 읽으려면 원리는 필요합니다.
| 정렬 | 평균 | 최악 | 추가 공간 | 안정성 |
|---|---|---|---|---|
| 퀵 정렬 | O(N log N) | O(N²) | O(log N) | 불안정 |
| 병합 정렬 | O(N log N) | O(N log N) | O(N) | 안정 |
| 힙 정렬 | O(N log N) | O(N log N) | O(1) | 불안정 |
퀵 정렬(quick sort) 은 기준값 하나를 골라 그보다 작은 값과 큰 값으로 배열을 갈라놓고, 양쪽에 같은 일을 반복합니다. 평균적으로 가장 빠르지만 기준값을 계속 한쪽 끝으로 고르면 분할이 되지 않아 O(N²)로 떨어집니다. 이미 정렬된 입력에서 첫 원소를 기준으로 삼으면 이런 일이 일어납니다.
병합 정렬(merge sort) 은 배열을 절반씩 쪼갠 뒤 정렬된 조각들을 합칩니다. 입력 형태와 무관하게 O(N log N)을 유지하고 안정적입니다. 대신 합칠 공간이 따로 필요합니다.
힙 정렬(heap sort) 은 힙을 만들어 최댓값을 하나씩 빼냅니다. 추가 공간을 거의 쓰지 않으면서 최악에도 O(N log N)입니다. 다만 메모리 접근 위치가 여기저기 흩어져 실측 속도는 퀵 정렬보다 느린 편입니다. 힙 자체는 ep.04 트리의 모양이 성능을 만든다에서 다룹니다.
실제 라이브러리는 하나만 쓰지 않습니다. V8은 배열 정렬에 팀소트(Timsort) 를 씁니다. 병합 정렬과 삽입 정렬을 결합한 방식으로, 입력에 이미 정렬된 구간이 있으면 그것을 찾아내 활용합니다. 안정성도 여기서 나옵니다.
O(N log N)보다 빠를 수 있는가
원소를 서로 비교해서 순서를 정하는 방식이라면 O(N log N)보다 빠를 수 없습니다. 증명은 경우의 수로 합니다. N개 원소의 가능한 순서는 N! 가지이고, 비교 한 번은 경우를 절반으로 줄이므로 최소 log₂(N!)번의 비교가 필요합니다. N이 10이면 10!은 3,628,800가지이고 log₂ 값은 약 22이므로 비교가 최소 22번 필요합니다. log₂(N!)을 정리하면 O(N log N)이 됩니다.
이 하한을 넘으려면 비교를 하지 않아야 합니다.
계수 정렬(counting sort) 이 그 방법입니다. 값의 범위가 0부터 K(코드의 max)까지로 좁을 때 쓰며, 세 단계로 진행합니다.
- 크기가 K + 1인 카운트 배열을 만듭니다
- 입력을 한 번 훑으면서 각 값을 인덱스로 삼아 몇 번 나왔는지 셉니다
- 카운트 배열을 0부터 K까지 차례로 읽으며 값 i를 count[i]번 출력합니다
입력이 3, 1, 4, 1, 5이고 K가 5면 2단계가 끝났을 때 카운트는 인덱스 0부터 [0, 2, 0, 1, 1, 1]이고, 3단계에서 이것을 읽어 내려가면 1, 1, 3, 4, 5가 나옵니다. 원소끼리 비교하는 단계가 없으니 하한에 걸리지 않습니다. 비용은 입력을 훑는 O(N)과 카운트 배열을 읽는 O(K)를 합친 O(N + K)입니다.
function countingSort(arr, max) {
const count = new Array(max + 1).fill(0);
for (const v of arr) count[v]++; // 값별 개수 세기
const result = [];
for (let v = 0; v <= max; v++) {
for (let i = 0; i < count[v]; i++) result.push(v);
}
return result;
}조건이 붙습니다. 값이 정수여야 하고 범위가 좁아야 합니다. 나이나 점수처럼 범위가 백 단위인 데이터에는 잘 맞고, 값이 수십억까지 벌어지면 카운트 배열이 메모리를 지나치게 차지합니다.
참고 자료
- Ecma International. (2019). ECMAScript 2019 Language Specification. Ecma International.
- MDN Web Docs. Array.prototype.sort(). Mozilla. https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
- V8. (2018). Getting things sorted in V8. https://v8.dev/blog/array-sort
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
다음 편 예고
같은 값을 같은 자료구조에 넣어도 넣는 순서에 따라 성능이 O(log N)과 O(N) 사이에서 갈립니다. 균형이라는 개념이 왜 필요한지, 그리고 자바스크립트에 없는 우선순위 큐를 어떻게 만드는지 봅니다.