TIL

JavaScript의 sort는 어떤 정렬 알고리즘을 사용할까?

기절초뿡 2022. 10. 30. 21:35

CS 스터디에서 sorting에 대해서 얘기를 하던 중, java에서는 sort 내장 메서드가 merge sort를 사용한다는 얘기를 들었다. JavaScript에서도 sort는 매우 자주 사용하는 메서드라, 어떤 정렬 알고리즘을 사용하는지 궁금해져 찾아보았다. 그 결과 JavaScript는 놀랍게도, 엔진에 따라서 다른 정렬 알고리즘을 사용한다는 사실을 알게되었다. ECMAscript 에 어떤 알고리즘을 써야하는지 특정하지 않았기 때문에, 브라우저마다 다른 정렬 알고리즘을 사용하는 것이다. 그래서 각 엔진은 어떤 정렬 알고리즘을 사용하는지 궁금해져 정리해보고자 했다.

1️⃣ V8 엔진

출처 - v8 기술 블로그

제일 먼저 알아볼 것은 Chrome 브라우저와 nodeJS 의 V8 엔진이다.
v8 엔진은 과거와 현재 다른 정렬 알고리즘을 사용하고 있다.

⛅ 우선 과거, V8 v7.0 및 Chrome 70 전에는 퀵 정렬과 삽입 정렬을 혼합하여 사용하였다.

  • 길이가 10 미만인 array의 경우 삽입 정렬
  • 그 외에는 퀵 정렬을 사용
  • 퀵 정렬에서 array를 분할해가는 과정에서 10 미만의 array가 생길 경우에도 삽입 정렬을 사용

 

🤔 왜 굳이 두 정렬을 혼용하여 사용하였을까?

- 퀵 정렬의 경우 분할한 뒤에 재귀 호출하기 때문에 오버헤드를 발생시키때문에, 짧은 array의 경우 삽입 정렬이 더욱 효과적이기 때문이다!

🍓퀵 정렬의 장점과 단점

  • 장점
    • 정렬하고자 하는 배열 안에서 교환하는 방식(제자리 정렬)이므로, 별도의 메모리 공간을 필요로 하지 않는다
  • 단점
    • 불안정 정렬(Unstable Sort) 이다
    • pivot을 최솟/최댓값으로 선택하는 경우나 이미 정렬되어 있는 경우 최악의 시간 복잡도를 가진다.(O(n^2)).
      • median of three 방식을 선택하여 첫번째, 중간, 그리고 마지막 값 중에서 중간값을 pivot으로 사용하는 방식을 사용했다.

 

🔆현재

V8 v7.0 및 Chrome 70 이후부터는 Timsort 라는 정렬 알고리즘을 사용하고 있다. Timsort 정렬 알고리즘에서는, 작은 단위일 때는 여전히 삽입 정렬을 사용하지만, 그보다 큰 array에서는 퀵 정렬 대신 합병(merge) 정렬을 사용한다.

Timsort를 사용하게된 이유
quick정렬은 불안정 정렬인 것에 반해, v8 bug tracker는 안정 정렬이 필요로 했기 때문이다. 그래서 현재는 안정 정렬인 Timsort를 사용한다.

🙄Timsort 이해한 대로 간단 요약
완전히 이해하기엔 아직 역부족이다...
- 앞서도 얘기했듯이, array의 길이가 짧을 때는 삽입 정렬의 효율이 매우 좋다.
- 전체를 작은 덩어리로 잘라 각각의 덩어리를 삽입 정렬로 정렬한 뒤, 합병 정렬로 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다.
- 2x개씩 잘라서 각각을 삽입 정렬로 정렬하면 덩어리별 xx개 병합 동작이 생략되어 그만큼 속도가 빨라진다.
- 최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 O(nlogn) 이다.
Timsort 관련하여 읽기 좋은 글


2️⃣ Spidermonkey 엔진

출처 - Searchfox
다음으로 알아볼 것은 mozilla/firefox 의 Spidermonkey 엔진이다.

  • 삽입과 합병 정렬을 혼용하여 사용한다.
  • array의 길이가 24 이하일 때는 삽입 정렬을 사용한다.
  • 그 이상의 길이의 array에서는 합병 정렬을 사용한다.

마찬가지로 짧은 길이일 때는 삽입 정렬을 사용했다. 

function MergeSort(array, len, comparefn) {
  assert(IsPackedArray(array), "array is packed");
  assert(array.length === len, "length mismatch");
  assert(len > 0, "array should be non-empty");

  // Insertion sort for small arrays, where "small" is defined by performance
  // testing.
  if (len < 24) {
    InsertionSort(array, 0, len - 1, comparefn);
    return array;
  }

  // We do all of our allocating up front
  var lBuffer = array;
  var rBuffer = [];

  // Use insertion sort for initial ranges.
  var windowSize = 4;
  for (var start = 0; start < len - 1; start += windowSize) {
    var end = std_Math_min(start + windowSize - 1, len - 1);
    InsertionSort(lBuffer, start, end, comparefn);
  }

  for (; windowSize < len; windowSize = 2 * windowSize) {
    for (var start = 0; start < len; 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, len - 1);

      Merge(lBuffer, rBuffer, start, mid, end, comparefn);
    }

    // Swap both lists.
    var swap = lBuffer;
    lBuffer = rBuffer;
    rBuffer = swap;
  }
  return lBuffer;
}

 

3️⃣ webkit 엔진

출처 - webkit 소스 코드
다음은 webkit/safari 의 경우이다.

  • string의 경우 버킷(bucket) 정렬 사용한다.
    • 버킷 정렬: 수많은 버킷에 배열 요소를 분산시킴으로써 동작하는 정렬 알고리즘
  • string이 아닐 경우 합병(merge) 정렬 이용한다.

자바스크립트의 sort는 기본적으로 사전식 정렬을 한다. 그래서 숫자를 정렬할 때도 compare 함수를 전달하지 않으면 string처럼 사전과 같이 정렬을 한다. 그 특징이 여기에서도 드러나있다. comparator가 undefined일 경우 isStringsort가 true가 되어 sortBucketSort 함수를 호출하여 버킷 정렬을 하고, comparator가 존재할 경우 sortMergeSort 함수를 호출하여 합병 정렬을 한다. 

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를 처리하는 방법이 어찌 보면 다 다른 것처럼 보일 수 있지만, 작은 배열의 경우 삽입을 사용하고, 길이가 길어지면 quick이나 merge를 기반으로 한다는 점에서는 비슷했다. 다른 언어의 경우는 어떨지도 궁금해져 찾아보니 자바는 merge sort,  c++ 의 경우 quick sort, 파이썬의 경우 Timsort 를 사용한다고 한다. 언어 전반적으로 sort 의 정렬 알고리즘은 크게 다름 없이 비슷하게 사용함을 알 수 있었다.

저작자표시 비영리 변경금지