[자바스크립트] Array.sort()에 대하여 (feat, 브라우저)

이번 포스트에서는 자바스크립트의 sort에 대해서 알아보고 브라우저별로 속도를 비교해보겠다.

일단 자바스크립트의 sort는 말 그대로 정렬해주는 것이다. 간단한 예를 봐보자

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]

코드로 보다시피 대상이 되는 배열을 정렬하는 것이다. 근데 정렬된 값을 보니 이상한 것이 있다. 바로 

 expected output: Array [1, 100000, 21, 30, 4]

 내가 아닌 상식선에서 1, 4, 21, 30, 100000으로 나와야 하는데 이상하게 되었다.

그 이유는 정렬이 되는 기준이 숫자가 아닌 문자열이기 때문이다.

기본 정렬 순서는 오름차순으로, 요소를 문자열로 변환 한 다음 UTF-16 코드 단위 값의 시퀀스를 비교합니다.

문자열로 비교를 하니 당연히 100000이 다른 숫자로 시작하는 문자열보다 앞에 오는 것이 맞다.

이러한 점 때문에 숫자의 오름차순으로 비교를 하려면 약간의 트릭이 필요한데. 바로 정렬의 기준을 재정의해주는 것이다.

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

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

이제는 정렬이 제대로 동작한다. 

---

여기서 한번 더 깊게 들어가보자.

그럼 undefined, null 이 들어간 배열은 어떻게 정렬될까?

let array = [1, 30, 4, 21, 100000, undefined, null];
array.sort((a,b)=>a-b) // [null, 1, 4, 21, 30, 100000, undefined]
array.sort((a,b)=>b-a) // [100000, 30, 21, 4, 1, null, undefined]

일단 undefined 경우 배열의 가장 뒤로 정렬되고, null은 가장 작은 값이라고 판단한다.

그럼 음수보다 작을까? 0보다는?

let array = [1, 30, 4, 21, 100000, undefined, null, 0, -0, -1];
array.sort((a,b)=>a-b) // [-1, null, 0, 1, 4, 21, 30, 100000, undefined]
array.sort((a,b)=>b-a) // [100000, 30, 21, 4, 1, null, 0, -1, undefined]

array.sort() // [-1, 0, -0, 1, 100000, 21, 30, 4, null, undefined]

보시다시피 0과 음수 사이에 있는 값으로 취급함을 알 수 있다.

근데 또 기본 정렬로 하게 되면 null은 undefined 뒤에 온다. 이것은 UTF-16 코드 단위 값의 시퀀스로 인해 생기는 차이임으로, 그냥 그렇다고 생각하면 된다.

그렇다면 값이 아닌 객체를 비교하면 정렬하고자 하면 어떻게 할까?

let stocks = [
  { name: "speh2kp8v2n", price: 9113 },
  { name: "sjaxfbzwbb", price: 4024 },
  { name: "8eilpq6y163", price: 323 },
  { name: "hdfev1mbn6d", price: 2399 },
  { name: "qgxtc1f2lk", price: 952 },
  { name: "09mlswca91e", price: 9948 },
  { name: "6pv83v384nx", price: 5507 },
  { name: "2mlufev39xd", price: 8480 },
  { name: "lifqojxpxur", price: 9763 },
  { name: "80pga2wzc1", price: 5367 },
];

  stocks.sort((a, b) => a.price > b.price ? 1 : -1);

price를 기준으로 오름차순으로 적절히 정렬된 것을 확인할 수 있다.

---

근데 MDN sort를 읽다 보면 상단에 다음과 같은 문구가 있다.

정렬의 시간 및 공간 복잡성은 구현에 따라 다르므로 보장할 수 없습니다.

구현에 따라 다르다고? 우리가 아는 sort 기준은 a, b를 대소 비교해서 정렬하는 건데 뭐가 다르다는 거지?

코드를 돌려서 확인해보자.

let stocks = [
  { name: "speh2kp8v2n", price: 9113 },
  { name: "sjaxfbzwbb", price: 4024 },
  { name: "8eilpq6y163", price: 323 },
  { name: "hdfev1mbn6d", price: 2399 },
  { name: "qgxtc1f2lk", price: 952 },
  { name: "09mlswca91e", price: 9948 },
  { name: "6pv83v384nx", price: 5507 },
  { name: "2mlufev39xd", price: 8480 },
  { name: "lifqojxpxur", price: 9763 },
  { name: "80pga2wzc1", price: 5367 },
];
let count = 1;
stocks.sort((a,b) => {
	console.log(count++,a,b)
	return a.price > b.price ? 1 : -1
})

오른쪽이 크롬, 왼쪽이 파이어폭스에서 실행한 결과이다.

보면 22번, 25번으로 비교하는 횟수 자체가 다르다. 이렇듯 브라우저가 제공하는 자바스크립트 엔진에 따라 내부 sorting 이 다르게 되어 있음을 확인할 수 있다.

---

그렇다면 각각의 브라우저별로 시간은 얼마나 걸릴까?

for (let repeat = 0; repeat < 10; repeat++) {
  let stocks = [];
  for (let i = 0; i < 1000000; i++) {
    stocks.push({ name: Math.random().toString(36).substr(2, 11), price: Math.floor(Math.random() * 10000) + 1 });
  }
  console.time();
  stocks.sort(function (a, b) {
    return a.name > b.name ? 1 : -1;
  });
  console.timeEnd();
}

크롬, 웨일, 엣지, 익스플로러, 파이어폭스 순

크롬, 웨일, 엣지는 속도가 비슷비슷한데 익스플로러와 파이어폭스는 2배 이상까지도 속도가 차이 남을 확인할 수 있다.

각각의 브라우저가 어떤 정렬 알고리즘을 썼는지는 예전에 본 글이 있어 기억이 가물가물하다. 

대충 크로미움 기반(크롬, 웨일?)은 퀵 소트, 파이어폭스, 사파리는 머지 소트라는 글을 본 거 같은데 언급했다시피 정확하지 않다. 조사를 해보고 딱 나오면 다시 업데이트해보겠다.

---

이번 포스트에서 각 브라우저별로 정렬 알고리즘을 다르게 사용하는 것을 확인했다. 솔직히 어떤 알고리즘이 가장 빠른지는 어떤 값이냐에 따라서 다르기 때문에 각 브라우저 엔진을 만드는 사람의 취향? 방향 차이라고 볼 수 있다.

다만 따라서 우리는 ECMA 스크립트에 따라 정렬의 기준만 제대로 정의해서 넘겨주면 된다.

여기서 말한 정렬의 기준은

  stocks.sort(function (a, b) {
    return a.name > b.name ? 1 : -1; // <- 요기부분
  });

우리는 여기서 1과 -1이라는 값을 기준으로 삼았다. 

다만 ECMA 표준은

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

위의 상황을 권장한다. 

가끔씩 1,-1이 아닌 true, false로 값을 넘기는 경우가 있는데, 이건 돌아갈 때도 있고 돌아가지 않을 때도 있어서 위험한 코드라고 할 수 있다.

따라서 우리가 사용했던 삼항 연산자를 이용한 코드를 사용하는 게 가장 깔끔하고 많은 스택오버플로어에 계신 형님들도 추천하고 계신 방법이다.