230322 TIL

💫오늘의 깨달음

1. 자바스크립트 sort()

자바스크립트의 sort() 메서드는 "퀵 정렬"로 구현되어 있는줄 알았는데, V8 엔진에서는 "삽입 정렬"과 "합병 정렬"을 결합하여 만든 정렬 알고리즘인 "Tim sort"로 구현되어 있다고 한다. 그리고 브라우저마다 sort() 구현의 알고리즘이 다르다고 한다. 파이어폭스의 경우 "합병 정렬"을 사용한다고 한다.

sort() 메서드를 사용할 때 전달인자인 compareFunc()을 제공해도 되고 안해도 되는데, 비교함수를 제공하지 않을 경우 요소를 자동으로 ASCII 문자를 기준으로 오름차순 정렬한다. 즉, "[1, 4, 3, 10, 2, 5]"의 배열을 오름차순으로 정렬할 때 비교함수를 제공하지 않을 경우 "[1, 10, 2, 3, 4, 5]" 순으로 정렬이 된다.

compareFunc(elem1, elem2)를 제공할 때는 첫 번째 요소가 두 번째 요소보다 우선순위가 높으면 음수를 반환해주고, 낮으면 양수롤 반환해주는 함수를 작성하면 된다. 같다면 0을 반환해주면 된다.

이러한 비교 방식을 "Three-way comparison"이라고 한다.

[JS] sort는 어떤 알고리즘을 사용할까?
Three-way comparison
V8 Tim sort docs
MDN : compreFn

정리

대부분의 정렬 알고리즘은 퀵 정렬로 구현되어 있는 줄 알았는데... "Tim Sort" 정렬 알고리즘은 처음 알게 되었다.
sort() 메서드를 사용할 때는 비교함수를 같이 사용하자.