[JS] 정렬과 비교함수에 대한 고찰

⭐ 시작에 앞서

자바스크립트의 sort 함수를 사용하다가 비교함수를 작성하는 데 문득 여러 가지 의문점과 납득 안 되는 동작들에 대해서 궁금증에 생기기 시작했다. 이와 관련해서 최근에 관련된 질문을 올렸는데 비추천을 받고 다시 생각해 보는 계기가 되었고 지금까지는 단순히 패턴처럼 사용했던 정렬과 비교함수를 좀 더 자세하게 분석하고 정리해 보려 한다.

💡 정렬과 비교함수

Array.prototype.sort([compareFunction])

sort함수는 JS의 초창기 버전 부터 있던 오래된 메소드로 원본 배열을 변환하는 대표적인 메소드이다. compareFunction은 정렬순서를 정의하는 비교함수로 구체적인 비교를 위해 사용할 수 있고, 비교함수를 생략하면 배열의 각 요소를 문자열로 변환하여 각 요소의 유니코드 값으로 비교하여 오름차순으로 정렬된다

굉장히 최근에 추가된 원본 배열을 변환하지 않고 새로운 배열을 생성하는 Array.prototype.toSorted 메소드도 존재하지만 비교함수에 대한 동작은 결국 같기 때문에 이 글에선 sort를 중심으로 다루도록 한다.

⭐ 비교함수에 대한 의문

우리는 정렬의 기준을 위해서 비교함수를 작성하기만 하면 이러한 기준에 따라서 내부적으로 배열이 정렬되므로 내부 동작 원리를 알 필요가 없지만, 비교함수를 작성하다가 어떤 순서로 어떻게 정렬되는지 궁금증을 갖게 되었다.

[5, 10, 6, 13, 9].sort((a, b) => -1);

가령 위의 코드처럼 아주 극단적인 상황을 가정해 보자.

비교함수에서 음수를 반환하면 a가 b보다 더 낮은 인덱스로 정렬되는데 이 함수는 항상 -1을 반환하니까 비교될 때마다 항상 a가 왼쪽으로 정렬된다.

하지만 위와 같은 규칙이라면 a, b 각각 어떤 값이 어떤 순서로 들어오냐에 따라서 정렬된 결과가 달라질 수 있는 거 아닌가 하는 의문이 든다. 그렇다면 확률에 기반하여 결과값이 달라지는 건가 싶지만 실제로는 내부 알고리즘에 따라서 항상 같은 순서로 a, b값이 들어오기 때문에 결과는 항상 동일하다.

⭐ 내부 동작과 알고리즘

Array.prototype.sort 함수의 ECMA 스펙을 보면 sort 함수의 내부 동작을 두가지 추상 연산을 통해서 설명하는 것을 볼 수 있다.

CompareArrayElements(x, y, comparator)

SortIndexedProperties(obj, len, SortCompare, holes)

쉽게 말하면 첫 번째 추상 연산 CompareArrayElements은 실질적으로 비교가 일어날 때마다 실행되는 연산으로, 두 요소를 받아서 비교 함수를 통해 반복적으로 호출되는 연산이고, 두 번째 연산 SortIndexedProperties는 배열의 요소들에서 어떤 순서로 정렬 대상을 추출하여 정렬 후에 어떻게 다시 배열에 채워 넣을지를 정의한다. 이 연산이 필요한 이유는 일반적인 배열뿐만 아니라 유사배열 객체나 희소배열의 경우도 일관되게 동작하는 sort 메소드의 전반적인 동작을 설명한다.

즉, CompareArrayElements는 비교함수의 호출이고 SortIndexedProperties는 전체 요소들을 어떻게 정렬할지에 대한 정렬 알고리즘이 적용되는 부분이다. ECMA 스펙은 비교 함수와 정렬 절차를 분리해 규정하지만, 정렬 알고리즘 선택은 구체적으로 정의하지 않고, 비교함수의 일관성만을 요구하며, 구체적인 구현은 자바스크립트 엔진에 위임하고 있다.

💡 일관된 동작 보장하기

사실 비교함수의 인자로 들어오는 a, b는 예측할 수 없다. 명세서상에 이 내용이 정의 되어있지도 않으며 그 순서는 엔진에 의해서 결정되기에 내부 구현이나 정렬 알고리즘에 따라 달라질 수 있어서 정확히 어떤 순서로 비교할지 알 수 없는 것

[1, 2, 3, 4, 5].sort(console.log);
// Chrome : 2 1, 3 2, 4 3, 5 4
// Firefox : 1 2, 2 3, 3 4, 4 5

위의 코드에서 a, b의 순서쌍을 콘솔에 출력시켜보면 각각 순서가 다르게 나오는것을 볼 수 있다. 비교함수는 내부 알고리즘에 의해 동작하기 때문에 내부적으로 호출 순서나 횟수가 달라질 수 있다. 따라서 비교 함수는 인자의 순서나 호출 횟수에 의존해서는 안 된다.

⭐ 일관되지 못한 동작

아래의 코드는 내가 스택 오버플로우에 직접 질문했던 코드이다. arr라는 배열을 isLeft라는 속성여부에 따라서 항상 왼쪽으로 정렬할 수 있을지에 대한 의문에서 시작하여 arr2와 arr3 배열은 어떤 속성을 확인하는지만 다를 뿐 isLeft의 여부에 따라서 각각 a의 속성과 b속성을 확인하고 정렬하는 것처럼 보인다.

const arr = [
  { isLeft: false, value: 5 },
  { isLeft: false, value: 18 },
  { isLeft: false, value: 3 },
  { isLeft: true, value: 10 },
  { isLeft: false, value: 8 },
];

const arr2 = [...arr].sort((a, b) => {
  if (b.isLeft) return 1;
  return a.value - b.value;
});

const arr3 = [...arr].sort((a, b) => {
  if (a.isLeft) return -1;
  return a.value - b.value;
});

// Chrome
console.log(arr2.map((v) => v.value)); // [3, 5, 10, 8, 18]
console.log(arr3.map((v) => v.value)); // [10, 3, 5, 8, 18]

솔직히 결과에 대한 확신은 없었지만 적어도 arr2와 arr3의 결과가 동일할 것으로 예상했었다. 하지만 두 배열의 정렬 결과는 달랐는데 무엇이 문제였을까?

⭐ 비교함수의 조건

명세서에 따르면 비교 함수의 안정적인 정렬을 위해서 아래와 같은 조건을 만족해야한다고 정의되어 있는데 sort 함수의 핵심인 비교함수를 작성함에 있어서 일관된 동작을 보장하기 위해서 굉장히 중요한 조건들이다.

• 동일한 입력 쌍은 항상 동일한 결과를 반환 (Stable)
• 결과는 반드시 NaN이 아닌 숫자
• 사이드 이펙트가 없는 순수함수
• 반사성, 대칭성, 추이성의 특징을 만족

위 문제의 코드로 돌아가보면 우선 비교함수의 작성 자체가 잘못되었다.

나는 비교함수가 a, b의 비교에서 양수, 음수, 0을 적절하게 반환하기만 하면 된다고 생각했지만, 모든 상황에 일관되게 작성해야한다. JS엔진에서 정렬을 어떤 알고리즘으로 실행하는지에 따라서 인자에 값이 어떤 순서로 들어올지 알수 없는데 지금 코드는 a, b가 각각 어떤 속성이 들어오냐에 따라서 다른 동작을 하므로 이는 올바른 비교함수가 아니어서 유효하지 않은 결과를 얻게 된 것

const arr4 = [...arr].sort((a, b) => {
  if (a.isLeft && !b.isLeft) return -1;  
  if (!a.isLeft && b.isLeft) return 1; 
  return a.value - b.value;
});

console.log(arr4.map((v) => v.value)); // [10, 3, 5, 8, 18]

예시 코드자체가 좀 억지스러운 면이 있지만 굳이 수정해 보자면 이런식으로 한가지 속성이 아닌 a, b 두가지 속성을 모두 확인하여 모든 조합을 분기 처리하는 식으로 해결할 수 있는데, 이렇게 하면 어떤 순서로 들어와도 항상 일관된 비교를 보장받을 수 있다.

💡 Stable Sort

Stable 정렬이란 같은 값들 사이의 상대적인 순서가 정렬 이후에도 똑같이 유지되는 정렬 알고리즘을 의미한다.

const students = [
  { name: "A", grade: 15 },
  { name: "B", grade: 15 },
  { name: "C", grade: 13 },
  { name: "D", grade: 14 },
];

위의 코드에서 grade를 기준으로 오름차순 정렬을 하면 [13, 14, 15, 15]와 같이 정렬되지만 여기서 같은 grade값을 갖는 A와 B가 정렬 이전의 순서와 똑같은 순서를 보장받도록하여 정렬 이후에도 A - B 순서를 유지하는 것을 Stable 정렬이라고 한다.

이게 어떻게 보면 당연한거 아닌가 하고 생각할 수 있지만 정렬 알고리즘에 따라서 정렬이 Stable일지 Unstable일지 달라질 수 있는데 ES10 이전에는 이러한 스펙이 정의되지 않아서 Stable 정렬을 보장하지 않았고 ES10 이후로 sort 함수의 Stable 정렬이 보장받을 수 있게 수정되었다.

💡 배열이 아닌 객체의 정렬

Array.prototype의 메소드들은 기본적으로 배열만을 위한 게 아닌 length를 가진 유사 배열에서도 사용할 수 있도록 만들어져 있는 Generic 메소드 이다.

sort 또한 객체의 length 속성과 인덱스로 사용되는 key-value 쌍을 모두 가져와서 새로운 배열로 다시 정렬하여 반환한다.

const arrayLike = {
  length: 4,
  0: 5,
  1: 1,
  3: 4,
};
console.log(Array.prototype.sort.call(arrayLike));
// {0: 1, 1: 4, 2: 5, length: 4}

여기서 재밌는 점은 키값으로 쓰이는 인덱스가 0 ~ length-1 범위의 인덱스가 아니면 length 뒤로해서 끝으로 정렬되며, sort 메소드가 일반 배열에서 원본 배열을 수정하는 것과는 다르게 arrayLike 객체는 결과가 덮어씌워지지 않고, 인덱스로 쓰인 키를 가져와서 새로운 배열을 만들어 0부터 순서대로 채워진다.

💡 마무리

sort 함수를 사용하다가 단순히 비교함수의 인자로 들어오는 a, b에 대한 일관성에 대한 궁금증에서 시작한 글이었다. 하지만 좀 더 파고들수록 비교함수가 실수하기 쉽고 놓치기 쉬운 디테일이 있었다고 생각한다.

비교함수는 단순히 비교를 위한 규칙을 떠나서 논리적으로 완전한 일관성을 갖고 비록 a, b는 예측할 수 없어도 그 결과는 항상 동일하게 하는게 중요하다고 생각한다. 깊이 생각해 보지 않았던 sort함수 였지만 생각보다 정교한 논리가 담겨있는 흥미로운 시간이었던 것 같다.

📕 참고 문서

1. MDN - Array.prototype.sort()
2. Stackoverflow - Sorting in JavaScript: Shouldn't returning a boolean be enough for a comparison function?
3. Stackoverflow - What are the arguments of "compareFunction" in sort of Array in JavaScript?