정렬을 할 때 Array.prototype.sort()를 사용하곤 하는데요.
시간복잡도가 평균 O(n log n)이라는 내용을 보고 문득 이런 궁금증이 생겼습니다.
'sort 메서드는 과연 어떤 정렬 알고리즘을 사용할까?'
지금부터 같이 알아보시죠!
먼저 다음 내용을 알아두셔야 합니다.
자바스크립트 엔진에 따라 sort 메서드 내부적으로 사용되는 정렬 알고리즘이 다르다.
각 엔진 별로 어떤 정렬 알고리즘을 사용하는지 간단하게 알아보겠습니다.
1. V8 (Chrome, Edge, Node.js)
버전 7.0 이전에는 Insertion Sort와 Quick Sort를 사용했습니다.
The basis is a Quicksort with an Insertion Sort fall-back for shorter arrays (length < 10). The Insertion Sort fall-back was also used when Quicksort recursion reached a sub-array length of 10.
Quick Sort에는 다음과 같은 치명적인 단점이 있습니다.
- 최악의 경우 시간 복잡도가 O(n^2)이다.
- stable sort를 보장하지 않는다.
V8 엔진은 많은 고민 끝에 기존의 Quick Sort를 버리고 Tim Sort를 사용하기로 합니다.
TimSort는 입력 길이에 따라 run이라고 불리는 최소 실행 길이가 정해지는데요. 길이가 run보다 작을 때는 Insertion Sort를, 그보다 클 때는 Merge Sort를 사용합니다.
Tim Sort 특징은 다음과 같습니다.
- 부분적으로 정렬된 데이터에 대해 매우 빠른 속도를 보여준다.
- stable sort를 보장한다.
- 최악의 경우 시간복잡도가 O(n log n)이다.
- 입력 크기에 비례하여 공간을 할당하므로 공간 효율성이 높다.
https://v8.dev/blog/array-sort
Tim Sort 관련 글
https://d2.naver.com/helloworld/0315536
https://github.com/python/cpython/blob/main/Objects/listsort.txt
https://en.wikipedia.org/wiki/Timsort
2. SpiderMonkey (Firefox)
Merge Sort를 사용합니다.
https://github.com/mozilla/gecko-dev/blob/master/js/src/builtin/Array.js
3. JavaScriptCore (Safari)
Merge Sort를 사용합니다.
https://github.com/WebKit/WebKit/blob/main/Source/JavaScriptCore/builtins/ArrayPrototype.js
sort 메서드에 사용되는 정렬 알고리즘을 확인해봤는데요.
같은 언어의 내장 메서드라도 자바스크립트 엔진마다 구현이 다르다는 점은 생각지 못한 부분이었습니다.
'Javascript' 카테고리의 다른 글
| JavaScript에서 Queue 구현하기: 배열 vs 연결 리스트 vs 두 개의 스택 (0) | 2023.10.23 |
|---|---|
| JavaScript에서 얕은 복사와 깊은 복사 이해하기 (0) | 2023.10.16 |
| JavaScript의 데이터 타입에 대해 알아보자! (0) | 2023.10.09 |
| JavaScript에서 변수란 무엇일까? (0) | 2023.09.25 |
| JavaScript에 대해 알아보자! (0) | 2023.09.16 |