Array.prototype.sort() 자세히 알아보기

자바스크립트 내부 배열 정렬 (Array.prototype.sort())

• sort() 메서드는 in place 메서드이다.
  • 입력값을 직접 변화시킨다. 입력 참조를 그대로 반환한다. 복사본을 만들지 않는다.
• 문자열을 넣으면 UTF-16 유니코드 값으로 정렬한다.
• 구현 방식은 자바스크립트 엔진에 따라 다르다.

예제

const months = ["March", "Jan", "Feb", "Dec"];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

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

파라미터

비교 함수 (compareFn) 를 받는다.

비교함수를 작성하지 않으면, UTF-16 유니코드 값을 기준으로 오름차순 정렬된다. undefined 는 맨 마지막에 온다.

비교함수 작성법

• compareFn(a, b) 반환 값을 기준으로
  • 반환 값 > 0: b 이후에 a 가 온다.
  • 반환 값 < 0: a 이후에 b 가 온다.
  • 반환 값 === 0: a, b 모두 위치를 유지한다.

개인적으로 a 를 뒤, b 를 앞이라고 생각한다.

• return b(앞) - a(뒤) 라면, 앞(a)이 더 크면 (b > a) 양수이니, 맨 앞에 가장 큰 값이 온다. (내림차순)
• return a(뒤) - b(앞) 라면, 앞(a)이 더 작아야 (b < a) 양수이니, 맨 앞에 가장 작은 값이 온다. (오름차순)

좋지 않은 비교함수

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? 1 : 0);
arr.sort(compareFn);

위 코드의 경우 V8 엔진이나 JavaScriptCore 엔진에서는 정렬이 하나도 안된다. 왜냐하면, compareFn 의 반환 값이 음수일 때만 위치를 스왑하게 해놓았기 때문이다.

배열이 아닌 오브젝트 정렬하기

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

• Function.prototype.call() 을 활용하면 된다. 기본적으로 this 의 length 를 기준으로 정렬하게 된다.
• 이를 이용하면, DOM 객체를 쥐고 있는 배열 등도 정렬 가능하다.

sort() 메서드는 어떤 정렬 알고리즘을 사용하는가?

• 구현에 따라 다르다.
  • V8 엔진에서는 TimSort 를 사용한다.
  • JavaScriptCore 엔진에서는 상황에 따라 다른 여러 정렬 알고리즘을 사용하는 것으로 보인다.

레퍼런스

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
https://woong-jae.com/javascript/220412-sort-implementation