Array.sort の浅析

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

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

デフォルトの sort メソッドは値を String に変換し、char code に従ってソートを行うため、上記の結果が得られます。

今日は、Javascript の sort の背後にある実装方法について探っていきます。

V8 の実装から、いくつかの事実を確認できます：

• Array の sort は quick 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
}

深堀り：なぜクイックソートなのか？

クイックソートの実装のポイントは、最悪の事態を避けるために相対的に良い pivot を選択することにあります。実際の状況では、入力データが必ずしもランダムではないため、実務上はランダムな方法で pivot を選択することが一般的です。

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

なぜマージソートではないのか？

マージソートは、まず配列を分解し、その後 merge を用いて継続的に統合する大きく分けて二つのステップから成ります。平均、最悪、最良の時間計算量はすべて $O(nlogn)$ に達し、アルゴリズム自体も安定しているのに、なぜ採用しないのでしょうか？

In-place

クイックソートでは、配列をマージする必要がなく、全体のアルゴリズムが追加の空間を消費せずに完了できますが、マージソートは $O(n)$ の空間を必要とします。したがって、クイックソートには上記のような状況があるにもかかわらず、実務上は依然として非常に良い選択肢です。

ランダム化の方法を用いることで（pivot のランダムな選択方法については、実際に大きな記事を書くことができます）、$O(n^2)$ の状況を避けることができます。

安定性

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

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

挿入ソート

V8 のソースコードを詳しく見ると、以下の一節を見つけることができます：

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

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

その理由を理解するために、挿入ソートの原理を思い出してみましょう。挿入ソートは、トランプの整理方法に似ており、毎回カードを一枚取り上げ、最適な位置を見つけて挿入します。挿入されるカードのグループはすでに整然としていますので、原位置でのソートが可能です。

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 が背後で行っていることを深く理解するようになりました。js がデフォルトで文字列比較に変換することに注意するだけでなく、大規模な配列のデータを処理する際には、背後の実装方式を理解することが非常に重要です。

また、異なるソートアルゴリズムにはそれぞれ適したシナリオがあることがわかりました。sort を使用する際には、以下のことを覚えておきましょう：

• クイックソートは実務上通常最良の結果を得られますが、クイックソートは安定したアルゴリズムではないことに注意してください。
• マージソートは $O(nlogn)$ の時間計算量を達成できますが、マージには追加の $O(n)$ の空間が必要です。
• 挿入ソートは少数の要素の配列をソートする際に良好な効果を示し、最良の場合は $O(n)$ で比較を完了できます。