javascript에서의 정렬
const array = [1,3,5,7,9];
array.sort(compareFunc);javascript에서의 정렬을 사용하면 어떤 내부 알고리즘을 사용할까 궁금해졌다.
기본적인 정렬들로 아래와 같은 정렬들이 있다.
여기서는 아래 정렬들을 설명하지는 않는다.
- selection sort
- bubble sort
- quick sort
- insertion sort
- shell sort
- merge sort
- heap sort
- radix sort
JS가 특정 알고리즘을 사용해야 한다는 요구사항은 없다.
JS엔진마다 각자의 정렬 알고리즘을 구현하여 사용한다.
JS엔진에는 어떤 것을이 있는지 간단하게 살펴보자
- chrome, Node의 V8
- 사파리의 웹킷
- 모질라(파이어폭스)의 스파이더 몽키
- 이밖의 Rhino, Chakra 등이 있다.
어떤 알고리즘을 사용하는지는 코드를 통해 확인 할 수 있으며, 추가적인 정보나 오픈소스가 아니라면 확인하기 힘들 것이다.
정렬알고리즘의 선택 방법.
정렬 알고리즘들을 비교할 때, 메모리를 얼마나 사용하는지 공간복잡도와 최악의 시간복잡도를 비교하게 된다.
또한 키 값이 같은 경우 상대 위치를 보장하는 안전 정렬과 불안전 정렬로 나뉠 수 있다.
각 브라우저는 하나의 정렬만 쓰는 것이 아닌 변수의 타입, 길이에 따라 여러가지 알고리즘을 사용하여 구현한다.
V8엔진의 sort
크롬은 chrome 70의 이전 버전에서는 아래와 같은 방법을 이용해 정렬을 사용했었다.
- 짧은 배열(길이 < 10)에 대한 insertion sort
- 길이가 길다면 Quicksort & 길이가 10 미만으로 내려간다면 insert sort 사용.
짧은 정렬에 대해서는 insert sort가 더 좋은 성능을 발휘하기 때문이다.
quick sort의 장점은 메모리 내에서 제자리 정렬이 된다는 것이다.
하지만 quick sort의 단점으로는 최소값 또는 최대값을 pivot으로 선택하는 경우 최악의 성능을 낸다.
- 이를 해결하기 위해 v8엔진에서는 배열의 첫 원소, 중간 원소, 마지막 원소 3개의 값을 선택하여 중간값을 찾는 알고리즘
- 더 큰 배열인 경우 샘플을 추출하고, 샘플을 정렬하여 중앙값을 마지막 원소를 대체하여 사용했습니다.
위와 같은 방식을 통해 최소값 또는 최대값이 피봇으로 선택되지 않도록 최악의 경우가 되는 피봇을 선택하지 않도록 해결하였다.
그럼에도 불구하고 quick sort는 불안정 정렬이라는 단점이 있다.
이후 버전에서는 Timsort 방식을 사용한다.
Timsort는 세부사항은 복잡하지만 기본사항은 이해하기 쉽다라는데
간단하게만 설명하자면,
- 작은단위는 insertion Sort, 큰단위는 MergeSort를 사용한다.
- MergeSort를 하기위해서 분리하는 단위인 RUN은 크기가 가변적이다.
- insertion Sort는 binary insertion sort를 사용하여 더 빠른 삽입 정렬이 가능하다.
Timsort는 좋은 글이 있어 대체 한다.
스파이더 몽키 엔진 sort
모질라/파이어폭스의 스파이더 몽키 엔진의 정렬 구현은 아래와 같다.
- 배열의 길이가 24 이하인 경우 삽입 정렬
- 기본적인 구현은 Merge Sort로 동작한다.
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;
}웹킷 엔진 sort
웹킷 엔진의 정렬 소스코드는 아래와 같으며
- @sortMergeSort기본적으로 merge sort를 이용한 안전 정렬을 사용한다
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;
}차크라 엔진 sort
아래는 차크라 엔진의 정렬 소스코드이며
- 배열의 길이가 512 이상이면 Quick sort를 진행한다.
- 배열의 길이가 512 보다 작다면 이분탐색을 이용한 삽입 정렬(binary insertion sort)을 이용한다.
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;
}
}
}ES2019의 안전 정렬
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
