Array.sort を紐解く

この記事は、JavaScript ネイティブの sort で注意すべき点について語るものではない。例えば：

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

デフォルトの sort メソッドは値を String に変換し、文字コードに従ってソートするため、上記のような結果になる。

今回は、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）を選択するかにある。実際の状況では、入力データがランダムであるとは限らないため、実務上はピボットをランダムに選択する方法が用いられることが多い。

最初の問題は、なぜ V8 はクイックソートを採用したのか？ ということだ。クイックソートの平均時間計算量は $O(nlogn)$ に達するが、最悪の場合は $O(n^2)$ になる可能性もある。また、クイックソートは安定なアルゴリズムではなく、同じ値を持つ2つのデータがソート後に相対的な順序を保てない可能性がある。

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

マージソートは大きく2つのステップに分けられる。まず配列を分解し、その後マージを呼び出して結合を繰り返す。平均、最悪、最善の時間計算量がすべて $O(nlogn)$ であり、アルゴリズム自体も安定しているのに、なぜ採用されなかったのだろうか？

In-place

クイックソートでは配列のマージ処理を行う必要がなく、アルゴリズム全体を追加のメモリ空間を消費せず完了できるのに対し、マージソートは $O(n)$ の空間を必要とする。そのため、クイックソートには前述のようなデメリットがあるものの、実務上は依然として非常に優れた選択肢となる。

ピボットをランダム化する手法によって（ピボットをどうランダムに選ぶかについては、それだけで1本の記事が書けるほどだが）、 $O(n^2)$ の発生を回避することができる。

Stable

しかし、それでもなお安定性の問題を解決することはできない。大半のユースケースではそれほど重要ではないかもしれないが（データのソートは通常バックエンド側で行われることが多いため）、もし直面した場合には非常に重要な考慮事項となる。

すべてのブラウザの実装がクイックソートを使っているわけではない

挿入ソート

V8 のソースコードをよく見ると、次のような箇所がある：

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

おや、なぜ配列の要素数が 10 以下のときに挿入ソートを使うのだろうか？

理由を理解するために、まずは挿入ソートの原理を振り返ってみよう。挿入ソートはトランプの手札を整理する方法とよく似ている。毎回カードを1枚手に取り、最適な位置を見つけて挿入する。挿入対象の手札は常にすでに整理された状態であり、In-place ソートを実現できる。

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 が裏側で何を行っているのかを深く理解するようになった。JavaScript がデフォルトで文字列に変換して比較することに注意するだけでなく、大量のデータを扱う配列を処理する際には、背後にある実装方式を理解することが極めて重要になる。

同時に僕たちは、ソートアルゴリズムごとにそれぞれ適した利用シナリオがあることも理解できた。sort を使う際には以下の点を覚えておきたい：

クイックソートは実務上において通常最良の結果をもたらすが、安定なアルゴリズムではない点に注意が必要である
マージソートは $O(nlogn)$ の時間計算量を達成できるものの、マージ処理のために追加で $O(n)$ の空間が必要となる
挿入ソートは要素数の少ない配列のソートにおいて優れた効果を発揮し、最善のケースでは $O(n)$ の比較で完了できる

カテゴリー

ページ

その他

Array.sort を紐解く