Array.sort の解析

この記事では、JavaScriptのネイティブなsortメソッドに注意すべき点については触れません。例えば：

;[1, 2, 3, 8, 20, 30, 11].sort()
// [1, 11, 2, 20, 3, 30, 8]

なぜなら、デフォルトのsortメソッドは値を文字列に変換し、文字コードに基づいてソートするため、上記の結果が表示されるからです。

今日はJavaScriptのsortメソッドの背後にある実装方法を探ってみましょう。

V8の実装からいくつかの事実がわかります：

Arrayのsortはクイックソートを使用してソートされます。
配列の要素数が10以下の場合、挿入ソートが使用されます。

V8のコードを簡略化するために、以下に簡単なクイックソートのコードを示します（参考までに）：

function quickSort(arr, p, r) {
  if (p < r) {
    var q = partition(arr, p, r)
    quickSort(arr, q - 1, p)
    quickSort(arr, q + 1, r)
  }
}

function partition(arr, p, r) {
  var x = arr[r]
  var i = p - 1
  for (var j = p; j < r - 1; j++) {
    if (arr[j] <= x) {
      i += 1
      var tmp = a[j]
      arr[j] = a[i]
      arr[i] = tmp
    }
  }
  var tmp = arr[r]
  arr[r] = a[i + 1]
  arr[i + 1] = tmp
}

探求：なぜクイックソートなのか？

クイックソートの実装のポイントは、最悪の場合を避けるためにどのように優れたピボットを選択するかです。実際の状況では、入力データは必ずしもランダムではないため、実践ではピボットをランダムに選択する方法が使用されます。

最初の問題は、「なぜV8はクイックソートを使用しているのか？」です。クイックソートは平均時間計算量が $O(n\log n)$ になる一方で、最悪の場合には $O(n^2)$ になる可能性があります。また、クイックソートは安定なアルゴリズムではありません。つまり、同じ値の2つのデータがソート後に異なる位置になることがあります。

なぜマージソートを使用しないのか？

マージソートは、配列を分割してマージを繰り返す2つの主要なステップに簡単に分けることができます。平均、最悪、最良の時間計算量はすべて $O(n\log n)$ に達するだけでなく、アルゴリズム自体は安定しています。なぜそれを採用しないのでしょうか？

インプレース

クイックソートでは、配列をマージする必要はありません。つまり、アルゴリズム全体を別の領域にコピーする必要がないため、追加のスペースを必要としません。一方、マージソートではマージに $O(n)$ のスペースが必要です。したがって、クイックソートには上記の問題が発生する可能性がありますが、実践的には非常に優れた選択肢です。

ランダムな方法（ピボットの選択方法に関しては、実際には詳細な説明ができるほどの量の記事が書けます）を使用することで、 $O(n^2)$ の状況を回避することができます。

安定性

ただし、安定性の問題は解決できません。ほとんどのシナリオでは重要ではないかもしれません（データのソートは通常バックエンドで処理されるため）。しかし、それが発生した場合、これは非常に重要な考慮事項です。

すべてのブラウザの実装がクイックソートを使用しているわけではありません

挿入ソート

V8のソースコードをよく見ると、次のコードがあります：

 while (true) {
  // Insertion sort is faster for short arrays.
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }

なぜ配列の要素数が10以下の場合に挿入ソートを使用するのでしょうか？

その理由を理解するために、挿入ソートの原理を振り返ってみましょう。挿入ソートは、トランプを整理する方法に似ています。1度に1枚のカードを取り上げ、適切な位置に挿入します。挿入するカードのセットはすでに整理されており、インプレースソートを実現できます。

function insertionSort(arr) {
  for (var j = 1; j < arr.length; j++) {
    var key = arr[j]
    var i = j - 1
    while (i >= 0 && arr[i] > key) {
      arr[i + 1] = arr[i]
      i = i - 1
    }
    arr[i + 1] = key
  }
  return arr
}

挿入ソートはバブルソートと同じ時間計算量を持っていますが、交換回数には大きな違いがあります。バブルソートは $O(n^2)$ の交換回数を持つ一方、挿入ソートは最大 $O(n)$ だけで済みます。

最初の質問に戻りましょう。「なぜ配列の要素数が10以下の場合に挿入ソートを使用するのでしょうか？」という問題です。

少数の要素で構成される配列では、すでにソートされているか、非常に近い順序で並んでいる場合、挿入ソートは時間計算量 $O(n)$ を達成できる唯一のアルゴリズムです。これは非常に効率的なことです。

結論

仕事上でソートが必要になったため、ネイティブのsortメソッドが行っていることを深く理解し始めました。デフォルトで文字列比較に変換されることに注意するだけでなく、大量のデータを処理する際には、背後にある実装方法を理解することが非常に重要です。

同時に、異なるソートアルゴリズムにはそれぞれ適したシナリオがあることを理解しましょう：

クイックソートは一般的に最良の結果をもたらしますが、クイックソートは安定なアルゴリズムではないことに注意してください。
マージソートは $O(n\log n)$ の時間計算量に達することができますが、マージに追加の $O(n)$ のスペースが必要です。
少数の要素で構成される配列のソートには挿入ソートが効果的であり、最良の場合は $O(n)$ で比較が完了します。

カランのブログ

配列.sort の分析