const array = [1,3,5,7,9];
array.sort(compareFunc);
javascript에서의 정렬을 사용하면 어떤 내부 알고리즘을 사용할까 궁금해졌다.
기본적인 정렬들로 아래와 같은 정렬들이 있다.
여기서는 아래 정렬들을 설명하지는 않는다.
JS가 특정 알고리즘을 사용해야 한다는 요구사항은 없다.
JS엔진마다 각자의 정렬 알고리즘을 구현하여 사용한다.
JS엔진에는 어떤 것을이 있는지 간단하게 살펴보자
어떤 알고리즘을 사용하는지는 코드를 통해 확인 할 수 있으며, 추가적인 정보나 오픈소스가 아니라면 확인하기 힘들 것이다.
정렬 알고리즘들을 비교할 때, 메모리를 얼마나 사용하는지 공간복잡도와 최악의 시간복잡도를 비교하게 된다.
또한 키 값이 같은 경우 상대 위치를 보장하는 안전 정렬과 불안전 정렬로 나뉠 수 있다.
각 브라우저는 하나의 정렬만 쓰는 것이 아닌 변수의 타입, 길이에 따라 여러가지 알고리즘을 사용하여 구현한다.
크롬은 chrome 70의 이전 버전에서는 아래와 같은 방법을 이용해 정렬을 사용했었다.
짧은 정렬에 대해서는 insert sort가 더 좋은 성능을 발휘하기 때문이다.
quick sort의 장점은 메모리 내에서 제자리 정렬이 된다는 것이다.
하지만 quick sort의 단점으로는 최소값 또는 최대값을 pivot으로 선택하는 경우 최악의 성능을 낸다.
위와 같은 방식을 통해 최소값 또는 최대값이 피봇으로 선택되지 않도록 최악의 경우가 되는 피봇을 선택하지 않도록 해결하였다.
그럼에도 불구하고 quick sort는 불안정 정렬이라는 단점이 있다.
이후 버전에서는 Timsort 방식을 사용한다.
Timsort는 세부사항은 복잡하지만 기본사항은 이해하기 쉽다라는데
간단하게만 설명하자면,
Timsort는 좋은 글이 있어 대체 한다.
모질라/파이어폭스의 스파이더 몽키 엔진의 정렬 구현은 아래와 같다.
function MergeSort(array, len, comparefn) {
// To save effort we will do all of our work on a dense list,
// then create holes at the end.
var denseList = [];
var denseLen = 0;
for (var i = 0; i < len; i++) {
if (i in array) {
DefineDataProperty(denseList, denseLen++, array[i]);
}
}
if (denseLen < 1) {
return array;
}
// Insertion sort for small arrays, where "small" is defined by performance
// testing.
if (denseLen < 24) {
InsertionSort(denseList, 0, denseLen - 1, comparefn);
MoveHoles(array, len, denseList, denseLen);
return array;
}
// We do all of our allocating up front
var lBuffer = denseList;
var rBuffer = [];
// Use insertion sort for initial ranges.
var windowSize = 4;
for (var start = 0; start < denseLen - 1; start += windowSize) {
var end = std_Math_min(start + windowSize - 1, denseLen - 1);
InsertionSort(lBuffer, start, end, comparefn);
}
for (; windowSize < denseLen; windowSize = 2 * windowSize) {
for (var start = 0; start < denseLen; start += 2 * windowSize) {
// The midpoint between the two subarrays.
var mid = start + windowSize - 1;
// To keep from going over the edge.
var end = std_Math_min(start + 2 * windowSize - 1, denseLen - 1);
Merge(lBuffer, rBuffer, start, mid, end, comparefn);
}
// Swap both lists.
var swap = lBuffer;
lBuffer = rBuffer;
rBuffer = swap;
}
MoveHoles(array, len, lBuffer, denseLen);
return array;
}
웹킷 엔진의 정렬 소스코드는 아래와 같으며
function sort(comparator)
{
"use strict";
var isStringSort = false;
if (comparator === @undefined)
isStringSort = true;
else if (!@isCallable(comparator))
@throwTypeError("Array.prototype.sort requires the comparator argument to be a function or undefined");
var receiver = @toObject(this, "Array.prototype.sort requires that |this| not be null or undefined");
var receiverLength = @toLength(receiver.length);
// For compatibility with Firefox and Chrome, do nothing observable
// to the target array if it has 0 or 1 sortable properties.
if (receiverLength < 2)
return receiver;
var compacted = [ ];
var sorted = null;
var undefinedCount = @sortCompact(receiver, receiverLength, compacted, isStringSort);
if (isStringSort) {
sorted = @newArrayWithSize(compacted.length);
@sortBucketSort(sorted, 0, compacted, 0);
} else
sorted = @sortMergeSort(compacted, comparator);
@sortCommit(receiver, receiverLength, sorted, undefinedCount);
return receiver;
}
아래는 차크라 엔진의 정렬 소스코드이며
static void hybridSort(__inout_ecount(length) Field(Var) *elements, uint32 length, CompareVarsInfo* compareInfo)
{
// The cost of memory moves starts to be more expensive than additional comparer calls (given a simple comparer)
// for arrays of more than 512 elements.
if (length > 512)
{
qsort_s(elements, length, compareVars, compareInfo);
return;
}
for (int i = 1; i < (int)length; i++)
{
if (compareVars(compareInfo, elements + i, elements + i - 1) < 0) {
// binary search for the left-most element greater than value:
int first = 0;
int last = i - 1;
while (first <= last)
{
int middle = (first + last) / 2;
if (compareVars(compareInfo, elements + i, elements + middle) < 0)
{
last = middle - 1;
}
else
{
first = middle + 1;
}
}
// insert value right before first:
Var value = elements[i];
MoveArray(elements + first + 1, elements + first, (i - first));
elements[first] = value;
}
}
}
This method sorts the elements of this array. The sort must be stable (that is, elements that compare equal must remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative Number if x < y, a positive Number if x > y, or a zero otherwise.
위 처럼 브라우저는 각자에 맞게 정렬방식을 구현하여, 상황에 따라 안전 정렬, 불안전 정렬을 사용하지만 ES2019부터는 정렬 방식이 안전 정렬로 동작 할 수 있도록 명세가 작성되어 있다.
https://stackoverflow.com/questions/234683/javascript-array-sort-implementation
https://v8.dev/blog/array-sort