[Javascript] sort() 내부 알고리즘

sort() 란?

배열의 요소를 정렬하는 데 사용하는 함수

배열의 요소를 적절한 위치에 정렬한 후에 그 배열을 반환한다. 또한 자바스크립트에서 sort함수는 default로 각 요소를 문자열로 변환하여 문자의 유니코드 순으로 정렬한다.

 

이러한 이유 때문에 다른 언어에서 사용하던대로 배열.sort() 구문을 사용했다가는 원하는 배열값이 나오지 않을 때가 있다. 예를 들어 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 배열을 오름차순으로 정렬하려고 한다. 우리가 원하는 정렬된 배열은 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이지만 정렬의 결과는 [1, 10, 2, 3, 4, 5, 6, 7, 8, 9] 가 된다. 

let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];

console.log(arr.sort());
// [1, 10, 2, 3, 4, 5, 6, 7, 8, 9]

sort함수에 매개변수를 주지 않으면 기본적으로 각 요소를 문자열로 바꿔서 비교하기 때문에 "10"과 "9"를 비교하면 "10"이 더 앞에 오게 되는 것이다.

따라서 우리가 원하는 대로 정렬을 하기 위해서는 sort함수에 매개변수 함수를 지정해주어야 한다.

sort() 구문 

자바스크립트 공식문서에서 정의하는 sort의 구문은 다음과 같다. 

* compareFunction을 감싸고 있는 대괄호는 생략가능하다는 의미이다. 

arr.sort([compareFunction])

---

compareFunction

정렬 순서를 정의하는 함수. 이를 생략하면 배열이 문자열 유니코드 값에 따라서 정렬된다.

반면에 compareFunction을 제공하면 배열 요소는 compareFunction의 반환 값에 따라서 정렬된다.

a와 b가 비교되는 두 요소라면 

 

- compareFunction(a, b) 이 0보다 큰 경우: a > b로 인식하고 두 요소의 위치를 바꾼다. 

- compareFunction(a, b) 이 0일 경우: a와 b를 변경하지 않는다.

- compareFunction(a, b) 이 0보다 작은 경우: a < b 로 인식하고 순서를 유지한다.

 

이러한 알고리즘을 이용해서 문자열 대신 숫자를 정렬하기 위해 compare 함수를 다음과 같이 구현할 수 있다. 

let arr = [10, 2, 5, 1, 3];

arr.sort(fuction(a, b) {
	return a - b;
})

console.log(arr); // [1, 2, 3, 5, 10]

문자열이 아닌 숫자 오른차순으로 잘 정렬된 것을 확인할 수 있다. 

 

내림차순으로 정렬하려면 b - a값을 반환하도록 하면 된다. 

let arr = [10, 2, 5, 1, 3];

arr.sort(fuction(a, b) {
	return b - a;
})

console.log(arr); // [10, 5, 3, 2, 1]

---

ES6부터 도입된 Arrow Function을 이용하여 더 간단하게 표현할 수 있다.

arr.sort((a, b) => a - b);

---

호기심 풀어보기
sort함수 내부에서는 어떤 정렬방식을 사용할까?

자바스크립트 명세에는 sort 구현에 어떤 알고리즘을 사용해야 한다고 특정하지 않는다. 따라서 자바스크립트를 해석하는 엔진을 어떻게 구현했냐에 따라 정렬에 사용되는 알고리즘이 달라질 수 있다는 것이다.

가장 많이 사용되는 V8엔진에서는 'Insertion Sort'과 'Merge Sort'를 결합하여 만든 Tim Sort 알고리즘을 사용한다.

Tim Sort 알고리즘은 시간복잡도 O(nlogn), stable, in-place 정렬로, java와 파이썬에서도 사용된다고 한다.

Tim sort 알고리즘에 대해 더 자세히 알고싶다면 여기를 참고하면 좋을 듯하다.

또한 파이어폭스에서 사용하는 'Spidermonkey'는 merge sort를 사용한다.

---

참고자료

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

https://noirstar.tistory.com/359

https://woong-jae.com/javascript/220412-sort-implementation