정렬: 비교 함수와 안정성

주문 관리 화면에 표가 있다. 행은 주문 시각 순으로 들어온다. 사용자가 "상태" 열 머리를 누르면 상태별로 모여야 하고, 같은 상태 안에서는 시각 순서가 그대로여야 한다. 그런데 QA에서 이런 보고가 올라온다. "같은 상태인 주문들 순서가 열을 누를 때마다 섞여요." "주문 번호 열을 누르면 10번이 9번보다 앞에 와요."

코드는 rows.sort(…) 한 줄이다. 정렬 알고리즘을 직접 짤 일은 드물지만, 정렬 함수에 무엇을 넘기는지는 매일 정한다. 이 장은 그 한 줄이 지켜 주는 것과 지켜 주지 않는 것을 본다. 알고리즘별 정의는 정렬 알고리즘, 병합 정렬, 퀵 정렬 노트에 있다.

기본 정렬: 문자열로 바꿔 비교한다

비교 함수: 음수, 0, 양수

숫자로 정렬하려면 비교 함수 compareFn(a, b)를 넘긴다. 돌려주는 값의 뜻은 정해져 있다(MDN: Array.prototype.sort).

그래서 오름차순 숫자 정렬은 (a, b) => a - b다. 빼기 한 번으로 세 경우가 다 나온다.

자주 보는 실수는 0을 돌려주지 않는 비교 함수다. (a, b) => a > b 같은 불리언 반환은 true/false가 1/0으로 바뀌어 음수가 나오지 않는다. TypeScript는 이 코드를 타입 오류로 막지만, JavaScript 파일에서는 그대로 돈다.

(a, b) => (a > b ? 1 : -1)은 반대로 0이 나오지 않는다. 같은 두 값을 a, b 자리를 바꿔 넣어도 둘 다 −1이 나와서 "a가 앞"이면서 "b가 앞"이라고 말하는 셈이다.

MDN은 이렇게 비교 함수의 규칙(같은 값끼리는 0, 순서를 뒤집으면 부호도 뒤집힘 등)을 어기면 동작이 정해지지 않고 엔진마다 결과가 달라진다고 적는다. 실제로 가격이 모두 같은 상품 a, b, c를 (x, y) => (x.price > y.price ? 1 : -1)로 정렬하면 Node.js 22(V8)에서는 c, b, a로 뒤집혀 나왔다. 같은 값이면 0을 돌려주는 것까지가 비교 함수의 일이다.

안정 정렬: 같은 키의 원래 순서

정렬 키가 같은 원소끼리 원래 순서를 지키는 정렬을 안정 정렬(stable sort)이라고 한다. 처음 장면의 "같은 상태인 주문들이 시각 순서를 지켜야 한다"가 바로 안정성이다.

ECMAScript 2019부터 명세가 Array.prototype.sort의 안정성을 요구한다(MDN: Array.prototype.sort). Python의 sorted와 list.sort도 안정 정렬을 보장한다(Python 문서: Sorting Techniques). 다만 안정성은 비교 함수가 같은 키에 0을 돌려줄 때만 의미가 있다. 앞 절의 ? 1 : -1처럼 0이 없으면 정렬 함수는 두 원소가 같다는 사실을 모른다.

안정성이 어디서 오는지 직접 짠 정렬로 보자. 삽입 정렬(insertion sort)은 앞쪽을 정렬된 상태로 유지하면서, 다음 원소 cur보다 큰 것을 한 칸씩 뒤로 밀고 빈자리에 cur를 넣는다. 핵심은 이 반복문이다. 행은 [상태 순위, 시각] 쌍이라 rows[j][0]은 앞 원소의 키, cur[0]은 지금 끼워 넣을 원소의 키다.

const cur = rows[i]
let j = i - 1
while (j >= 0 && rows[j][0] > cur[0]) { // 앞 원소의 키 > 지금 키인 동안
  rows[j + 1] = rows[j] // 앞 원소를 한 칸 뒤로 민다
  j -= 1
}
rows[j + 1] = cur // 멈춘 자리 바로 뒤에 넣는다

1const rows = [[2, '09:10'], [1, '09:20'], [2, '09:30'], [1, '09:40']]2for (let i = 1; i < rows.length; i++) {3  const cur = rows[i]4  let j = i - 15  while (j >= 0 && rows[j][0] > cur[0]) {6    rows[j + 1] = rows[j]7    j -= 18  }9  rows[j + 1] = cur10}11console.log(rows.map(r => r[1]).join(' '))

09:20 09:40 09:10 09:30

여러 키로 정렬하기

"상태 순으로, 상태가 같으면 시각 순으로"는 두 가지로 쓸 수 있다.

첫째, 비교 함수 하나에 키를 차례로 적는다. 앞 키의 비교가 0이면 다음 키로 넘어간다. JavaScript에서는 ||가 0을 거짓으로 보고 뒤 식을 계산하는 성질을 쓴다. Python은 key=에 튜플을 돌려주면 튜플이 앞 원소부터 비교되어 같은 효과가 난다. key 함수는 원소마다 한 번만 불린다(Python 문서: Sorting Techniques).

1type Order = { rank: number; time: string }2const sortedOrders = orders.toSorted(3  (a, b) => a.rank - b.rank || a.time.localeCompare(b.time),4)

둘째, 안정 정렬을 두 번 한다. 덜 중요한 키(시각)로 먼저 정렬하고, 중요한 키(상태)로 다시 정렬한다. 두 번째 정렬이 안정 정렬이라 같은 상태 안에서는 첫 번째 정렬의 시각 순서가 남는다. Python 문서도 이 방법을 예로 든다. 표 화면에서 사용자가 시각 열을 누른 다음 상태 열을 누르는 동작이 바로 이 방식이다. 지금 정렬 상태에 다음 열 정렬을 덧씌우기만 하면 된다.

두 가지를 더 챙긴다. sort는 배열을 그 자리에서(in place) 바꾸고 같은 배열을 돌려준다. React의 props나 상태 배열을 sort하면 원본이 바뀐다. 원본을 두고 새 배열을 받으려면 toSorted()를 쓴다(MDN: Array.prototype.sort). Python에서 list.sort()는 그 자리에서 바꾸고 None을 돌려주며, sorted()는 새 리스트를 돌려준다. 그리고 Python의 sorted는 key만 받는다. JavaScript식 비교 함수가 이미 있으면 functools.cmp_to_key로 감싸 key로 넘긴다(Python 문서: Sorting Techniques).

코드 리뷰: 상품 정렬 함수

정리하면 상품 정렬 함수에서 틀린 줄은 앞 절들의 세 실수다. 같은 값에 0이 없는 ? 1 : -1(2절), 원본을 바꾼 채 돌려주는 sort(4절), 비교 함수 없는 숫자 정렬(1절).

[3, 1, 2, 5, 4] → 3  (3 > 1, 3 > 2, 5 > 4)
[4, 3, 2, 1] → 6