코딩을 하다보면 sort를 여러번 사용해야하는 경우가 자주 발생한다. 특히 알고리즘을 풀다보면 시간초과(time out)가 되는 것을 종종 볼 수 있는데, sort 함수도 시간복잡도 계산에 포함되는 내용이기 때문에 신경을 써야하는 부분이다.
그래서 sort의 대해서 알아보다가 sort의 종류도 많고, 자바스크립트의 내장함수 sort는 여러 방식 중에 어떤 것을 사용하고 있을까 궁금해서 글을 끄적여 보게되었다.
sort는 여러 시리즈로 한 번 만들어보면 좋을 것 같다고 생각중이다.
🗃️ Array.prototype.sort()
평소 '오름차순이나 내림차순 정렬하려면, sort를 그냥 쓰면되지!' 라는 생각만 가지고 있었다가 문뜩 sort 함수가 어떻게 정렬되는지 궁금해졌다.
무튼 자바스크립트에서 배열을 정렬하고 싶을 때는 아래와 같이 sort 메서드를 사용한다.
arr.sort([compareFunc]);-
파라미터로
compareFunc(비교함수)를 제공해도 되고 안해도 된다. -
compareFunc(elem1, elem2)가 있다면,elem1(첫 번째 요소)가elem2(두 번째 요소)보다 우선순위가 높으면 음수를 반환하고, 낮으면 양수롤 반환해주는 함수를 작성하면 된다. 같다면 0을 반환해주면 된다. -
비교함수가 없으면, 요소를 자동으로
ASCII 문자를 기준으로오름차순정렬한다.
🧮 자바스크립트에서 사용하는 sort 알고리즘
자바스크립트 명세에는 sort 구현에 어떤 알고리즘을 사용해야 한다고 특정하지 않는다.
이 말은 자바스크립트를 해석하는 엔진을 어떻게 구현했냐에 따라 정렬에 사용되는 알고리즘에 달라질 수 있다는 것이다.
가장 많이 쓰이는 V8 엔진에서는 어떻게 구현했는지 찾아보자.
V8 깃허브에 가서 'sort'를 검색해보면 , third_party/v8/builtins/array-sort.tq라는 파일을 찾을 수 있다.
이 파일의 상단에 주석을 보면 아래와 같은 내용이 적혀져있다.
// This file implements a stable, adapative merge sort variant called TimSort.
"이 파일은 TimSort라는 안정적인 적응형 병합 정렬 변형을 구현합니다.".V8은 정렬 알고리즘으로 'Tim Sort'를 사용한다는 것을 알 수 있다.
🤔 Tim Sort 란?
2002년 소프트웨어 엔지니어 Tim Peters에 의하여 Tim sort가 등장했다.
이 정렬 알고리즘은 'Insertion Sort'과 'Merge Sort'를 결합하여 만든 정렬이라고 한다. 주석의 내용으로 추측할 수 있듯이 merge sort를 기반으로 엄청나게 최적화를 한 알고리즘이다.
실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn)이다.
Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.
Tim Sort는 다른 sort의 종류부터 알아야 적을 수 있는 내용으로, 마지막으로 따로 정리해서 끄적여 보도록 하겠다!
📕 정리
자바스크립트의 내부함수 sort가 이렇게 최적화를 잘 해놓았을 지는 몰랐는데, 다른 sort 방식보다 최적화가 잘 되어 있다는 것에 많이 놀랐다.
항상 알고리즘을 풀 때, sort를 따로 만들어서 써야하나 했었는데 그럴 필요가 없었던 것 같다. 오히려 필요하다면 sort 메소드를 쓰되, 최대한 덜 사용하여 답을 낼 수 있는 방법을 찾는게 맞다는 것을 느끼게 되었다.
