JavaScript 배열의 sort() 메서드

요즘에는 가능하면 코딩 테스트 문제를 JavaScript로 풀려고 한다. 언젠가는 정렬이 필요한 문제를 JavaScript로 풀었다. 한 부분만 빼고는 제대로 풀었는데, 그 한 부분을 잘못 작성해서 한 문제를 버리게 될 뻔했다. 다행히 다른 코너 케이스를 찾다가 얻어 걸려서, 배열의 sort() 메서드를 잘못 사용했다는 것을 발견했다.

Array.prototype.sort()의 사용법

메서드에 아무 인수도 주지 않으면 배열의 각 원소를 문자열로 취급하여 UTF-16 인코딩 기준 오름차순으로 제자리에서(in-place) 정렬한다. 그리고 정렬한 배열을 리턴한다. 정렬은 ES2019부터 stability가 보장된다.

const strings = ['Lorem', 'ipsum', 'dolor', 'sit', 'amet'];
const sortedStrings = strings.sort();
console.log(sortedStrings); // ['Lorem', 'amet', 'dolor', 'ipsum', 'sit']
console.log(strings); // ['Lorem', 'amet', 'dolor', 'ipsum', 'sit']
console.log(strings === sortedStrings); // true

정렬 방법을 설명한 문장과 예제에는 주의해야 할 부분이 다수 있는데, 그 부분은 조금 뒤에 다룰 것이다.

비교 함수 사용하기

메서드에 (a: any, b: any) => number 형태의 비교 함수를 인수로 주면, 규칙에 따라 정렬한다.

• (리턴 값) < 0: a가 b보다 앞에 온다.
• (리턴 값) = 0
  • (ES2019 스펙부터) a와 b의 순서를 유지한다.
  • (ES2019보다 과거 스펙에서) a와 b의 순서가 어떻게 되는 상관없다.
• (리턴 값) > 0: a가 b보다 뒤에 온다.
• 비교 함수의 리턴 값에 모순이 있으면 정렬 순서는 알 수 없다.

비교 함수를 정의하지 않으면 배열의 각 원소를 문자열로 취급하여 비교하므로, number[] 배열은 number 값 순서대로 정렬되지 않는다. MDN의 JavaScript 레퍼런스에 그 예제가 잘 나와 있다.

// Any copyright is dedicated to the Public Domain.
// http://creativecommons.org/publicdomain/zero/1.0/
// Source: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]

따라서 number[] 배열을 오름차순으로 올바르게 정렬하기 위해서는 다음과 같이 비교 함수를 전달해야 한다. (이 예제는 NaN, Infinity, -Infinity이 포함하지 않는 배열만 올바르게 정렬한다.)

const numbers = [1, 30, 4, 21, 100000];
numbers.sort((a, b) => a - b);
console.log(numbers); // [ 1, 4, 21, 30, 100000 ]

짚고 넘어가야 하는 주의사항

예제도, 설명도 별로 어렵지 않아 보이지만, 다음 내용을 주의깊게 생각하지 않으면 잘못 사용하기 좋다.

1. 비교 함수가 없다면 UTF-16 문자열로 취급하여 오름차순 정렬

UTF-16

맨 처음 예제의 정렬 결과에서 'Lorem'이 'amet'보다 먼저 나왔다. 두 문자열의 첫 글자인 L(U+004C)과 a(U+0061) 중 L이 먼저이기 때문이다. UTF-16으로 인코딩된 데이터 순서가 아니라 정말 사전순으로 정렬하려는 상황에는 String.prototype.localeCompare() 메서드를 활용하라고 MDN 문서에서 권고한다.

그렇다면 UTF-16에서 두 글자로 나누어 표현되는 문자(U+10000부터)는 어떻게 될까? 코드포인트가 아니라 나누어진 16비트 코드 유닛 단위로 비교하기 때문에 꼭 코드포인트 순서대로 정렬되지는 않는다. 코드포인트상으로는 🥳(U+1F973, Partying Face) 이모지가 Ａ(U+FF21, Fullwidth Latin Capital Letter A)보다 나중에 나온다. 하지만 JavaScript에서는 UTF-16 인코딩에 따라 🥳 이모지를 '\uD83E\uDD73'으로 취급한다. ('🥳'.length도 2이다.) 따라서 두 문자를 정렬할 때 '\uD83E'와 '\uFF21'을 비교하게 되고, 🥳 이모지가 Ａ보다 먼저 오도록 정렬한다. 코드포인트 순서대로 정렬하려면 별도의 비교 함수를 넘겨줘야 한다.

const withSmp = ['Ａ', '🥳']; // ['\uFF21', '\u{1F973}'];
console.log(withSmp.sort()); // [ '🥳', 'Ａ' ]

문자열

한편, 문자열이 아닌 것을 정렬하려면 앞에서 설명한 것처럼 비교 함수를 사용해야 한다. 이때 비교 함수의 리턴 값에 주의할 필요가 있다. 비교 함수는 결과가 0이거나, 0보다 작거나, 큰 값이 되도록 작성해야 한다. 비교 함수가 NaN 같은 값을 리턴하면(예: Infinity - Infinity) 올바른 정렬 순서가 보장되지 않는다.

2. ES2019부터 Stability 보장

MDN 영문 레퍼런스에 따르면, ES2019 스펙부터 Array.prototype.sort()의 stability가 보장된다고 한다. 정렬의 stability는 구현체가 비교 함수의 리턴 값을 0과 비교하는지에 따라 결정된다고 한다.

웹 브라우저별 stable sort 지원 여부는 MDN 레퍼런스 페이지와 caniuse.com 등에서 확인할 수 있다. IE와 레거시 Edge를 제외한 웬만한 주요 브라우저에서 stable sort를 지원한다. node.green에 따르면 Node.js에서는 12.0.0 버전부터 ES2019 스펙을 지원한다. 이 버전부터는 stable sort 지원이 보장된다.(표에 stable sort가 직접적으로 언급되지는 않음)

3. In-Place Sort: 원본 배열을 변경함

Array.prototype.sort()는 원본 배열을 변경한다. 첫 번째 예제를 다시 보자.

const strings = ['Lorem', 'ipsum', 'dolor', 'sit', 'amet'];
const sortedStrings = strings.sort();
console.log(sortedStrings); // ['Lorem', 'amet', 'dolor', 'ipsum', 'sit']
console.log(strings); // ['Lorem', 'amet', 'dolor', 'ipsum', 'sit']
console.log(strings === sortedStrings); // true

strings.sort()는 배열 strings 자체를 변경한 뒤에 자기 자신을 리턴한다. 따라서 sortedStrings는 strings와 (레퍼런스가) 동일한 배열이고, strings === sortedStrings는 true이다. 원본 배열을 변경하지 않으려면, 간단하게는 다음과 같이 원본 배열을 복제해서 정렬하는 방법을 쓸 수 있다.

const strings = ['Lorem', 'ipsum', 'dolor', 'sit', 'amet'];
const sortedStrings = [...strings].sort();
console.log(strings); // [ 'Lorem', 'ipsum', 'dolor', 'sit', 'amet' ]
console.log(sortedStrings); // [ 'Lorem', 'amet', 'dolor', 'ipsum', 'sit' ]
console.log(strings === sortedStrings); // false

4. 비교 함수의 일관성

당연한 얘기지만, 비교 함수는 모순되지 않는 결과를 리턴해야 한다. 그렇지 않으면 정렬 순서가 보장되지 않는다. 대소관계로 표현하긴 부적절해 보이지만, 예를 들어서 가위바위보에는 다음과 같은 상성이 있다. (큰 쪽이 작은 쪽을 이김)

• 가위 < 바위 — (1)
• 바위 < 보자기 — (2)
• 보자기 < 가위 — (3)

여기서 (1), (2)에 따르면 가위 < 보자기이지만, 이는 (3)에 모순이다. 이렇게 비교 함수의 리턴 값에 모순이 있으면 정렬 순서가 보장되지 않는다.

더 자세히 말하자면, 비교 함수 compareFn은 아래 속성을 모두 가지고 있어야 한다.

• Purity: 비교 함수는 비교 대상이나 외부 상태를 변경하지 않는다.
• Stability: 비교 함수는 같은 쌍의 입력에 대해서 같은 결과를 리턴한다.
• Reflexivity: 동일한 두 비교 대상을 입력으로 받은 비교 함수는 0을 리턴한다.
• Symmetry: 비교 함수가 어떤 두 비교 대상을 입력으로 받아서 0이나 다른 유효한 값을 리턴했다면, 두 비교 대상의 순서가 맞바뀌었을 때, 똑같이 0이나 부호가 반대인 값을 리턴한다.
• Transitivity: compareFn(a, b), compareFn(b, c)가 모두 양수이거나 0이거나 음수일 때, compareFn(a, c)도 같은 종류의 값이다.

5. 빈 슬롯과 undefined인 원소 처리

JavaScript 배열의 sort() 메서드에서는 빈 슬롯과 undefined를 다음과 같이 다룬다.

첫째, 비교 함수 전달의 유무와 관계없이 빈 슬롯과 undefined를 배열의 맨 뒤로 옮긴다. 이때 빈 슬롯이 undefined보다 뒤로 간다.

const items = ['default', /* empty */, 'function', 'typeof', undefined, 'var'];
// [ 'default', <1 empty item>, 'function', 'typeof', undefined, 'var' ]

items.sort();
console.log(items);
// [ 'default', 'function', 'typeof', 'var', undefined, <1 empty item> ]

둘째, 빈 슬롯이나 undefined 값으로는 비교 함수가 호출되지 않는다. 아래 예제는 비교 함수의 매개변수의 타입을 출력하도록 작성했지만, undefined는 출력되지 않는다.

const items = ['default', /* empty */, 'function', 'typeof', undefined, 'var'];
items.sort((a, b) => {
  console.log(`a: ${typeof a}    b: ${typeof b}`);
  if (`${a}` === `${b}`) {
    return 0;
  }
  return String(a) < String(b) ? -1 : 1;
});
// 정렬 도중 "a: string    b: string" 수 차례 출력
// [ 'default', 'function', 'typeof', 'var', undefined, <1 empty item> ]

위의 예제에 null을 끼워넣으면, null과 비교가 이루어지고(type이 object로 출력된다.) null이 정렬 결과의 중간 부분에 끼는 것을 볼 수 있다.

요약

Array.prototype.sort()는...

1. 비교 함수를 전달하지 않으면 UTF-16 문자열로 취급하여 오름차순으로 정렬한다.
2. ES2019부터 stable sort이다.
3. 원본 배열을 변경한다.
4. 비교 함수를 전달하여 실행할 때, 비교 함수가 일관적인 결과를 리턴해야 한다.
5. 빈 슬롯을 맨 뒤로, undefined를 그 앞으로 보낸다.

참고 자료

• Array.prototype.sort() — MDN Web Docs (English)
• Array.prototype.sort() — MDN Web Docs (한국어)
• Getting things sorted in V8 — V8 Blog