JavaScriptとQuickSort

Monacaチームの内藤です。
コロナであまり外出出来なくなり、家でYouTubeを見ることが多くなりました。そして、先日、関数型プログラミングの動画(https://www.youtube.com/watch?v=rIprO6zoujM)を見ていたのですが、そこでは次のようなコードが出てきました。

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
	let smallerOrEqual = [a | a <- xs, a <= x]
	    larger = [a | a <- xs, a > x]
	in quicksort smallerOrEqual ++ [x] ++ quicksort larger

（簡単のため、ピボットとして先頭要素を採用しています。再起呼び出しするときに、ピボットは含めていないので、これで問題なくソートが出来ます。実は動画にあるものとは少し違い、このコードは「すごいHaskell 楽しく学ぼう」という本から引用しました。実際の動作内容は同じです。）

これ、関数名を見ると気づかれるかと思いますが、実はクイックソートのコードです。クイックソートというと、プログラミングの学習の中では、再起処理を習うところで出てくることが多いと思いますが、Forループに展開出来ない非自明な再起処理の例としてよく使われていているものの、なんとなくコードが複雑で難しいなと思っていました。それが、こんなコンパクトに簡単に書けるって、ちょっと驚きでした。

実は、これにはタネあかしが一つあって、本来クイックソートというときは、外部ソートで実装されたものを指し、入力の配列をそのまま書き換えてソートさせている（つまり、ソート処理をするために新たな配列をヒープメモリ上にとらない）のですが、上で示したクイックソートは内部ソートになっていて、その分、簡潔に書ける様になっています。内部ソートだと簡潔に書ける代わりに、再起呼び出しをする度に新しく配列を作り直しているため、本来のクイックソートと比べると、処理速度・メモリ使用量ともに悪くなってしまっています。

とはいえ、時間計算量は最良O(n log n)〜最悪O(n^2)ですし、なにより、クイックソートのエッセンスを直感的に理解しやすくコード化されているのはすごいと思います。

上の処理を言葉で示すと、配列の第一要素をピボットとして、それより値以下の要素をsmallerOrEqual、ピボットより大きい値の要素をlargerとして、それぞれ再起的にクイックソートを適用しているだけになります。

さて、これは最も短いクイックソートの実装（内部ソートであることは別にして）ということらしいのですが、しかしそもそも、ここまで簡潔に書ける大きな要因としては、Haskellの持つパターンマッチや内包表記を使っているからでしょう。ではこれをJavaScriptで書き直したらどうなるでしょうか？

ということで、JavaScriptで書き直してみたところ、次の様になりました。

function quicksort (array) {
  if (1 >= array.length) return array;
  const [head, ...tail] = array;
  const smallerOrEqual = tail.filter(x => x <= head);
  const larger = tail.filter(x => x > head);
  return [...quicksort(smallerOrEqual), head, ...quicksort(larger)];
}

Haskellとほとんど変わらないくらい簡潔でした。
ES6から、スプリット構文が使える様になり、特に、arrayを最初の1要素と残りに分解するのが、[head, ...tail] = arrayと書けるのがすごくいい感じです。（注：ただし、Haskellはリストなので分割がO(1)で出来ますが、JavaScriptだと配列なので内部的にはO(n)の処理になると思います）
また、内包表記は使えないものの、アロー関数で簡潔に条件を記述出来るのも良いですね。

ちなみに、典型的な外部ソートのQuickSortは、例えば、次の様な感じになると思います。

function quicksort (array) {
  function impl(start, end) {
    if (start + 1 >= end) return;
    let [pivot, l, r] = [start, start, end - 1];
    while (l < r) {
      while (array[pivot] < array[r]) r--;
      while (array[l] <= array[pivot] && l < r) l++;
      [array[l], array[r]] = [array[r], array[l]];
    }
    [array[pivot], array[l]] = [array[l], array[pivot]]; 
    impl(start, l);
    impl(l+1, end); 
  }
  impl(0, array.length);
}

こちらも、分割代入を使っているのでC言語よりは簡単かなとは思います。
また、先頭要素（のインデックス）をピボットにしているのは前のコードと同じなのですが、ピボットより小さい要素と大きい要素を入れ替えるwhileループの処理が結構大変で、この部分が難しいので、全体的に難しく感じてしまいますね。
また、whileループの後にピボットを移動しているのは、再起呼び出しでピボットを含まない様にしないと無限ループしてしまう場合があるからだと思いますが、そのあたりもちょっと分かりにくいかなと思います。

最後に、処理足でどのくらいの差が出るかを測ってみました。(nodeでの実行です）配列の長さを100、1000、2000で、ランダムに整数値を入れてクイックソートを行い、それを1000回繰り返した結果です。（単位はミリ秒）

配列の長さ | 内部ソート | 外部ソート
100 | 42 | 27
1000 | 435 | 231
2000 | 1003 | 456

予想通りですが、やはり外部ソートの方が処理は早い結果になりました。この辺りは、今後将来、マルチスレッドやメモリ効率の最適化などが進んでいけば、同じくらいの結果になっていくのではないかなと思っています。