List comprehensionを使ったクイックソート

List comprehensionを使うと簡単にクイックソートができるらしい。というか、Programming Examplesにサンプルが載っているわけだけど、おもしろそうなので勉強がてら再発明してみた。

クイックソートのアルゴリズム

1. 適当な数（ピボットという）を選択する（データの中央値が望ましい）
2. ピボットより小さい数を前方、大きい数を後方に移動させる（分割）
3. 二分割された各々のデータを、それぞれソートする

これを、List comprehensionを使ってやるならこんな感じかな。

配列の先頭をピボットとして取り出す。
残りの配列からピボットより小さい値の配列を取り出す。
- 取り出した配列が空になるまで再帰してソートする。
残りの配列からピボットより大きい値の配列を得る。
- 取り出した配列が空になるまで再帰してソートする。
「ピボットより小さい値の配列(ソート済み) + ピボット + ピボットより大きい値の配列(ソート済み)」を連結して返す。

実装

ということで実装してみた。

-module(sort).
-export([sort/1, sort2/1]).

sort([]) -> [];
sort([Pivot|List]) ->
  Lt = sort([ Item || Item <- List, Item <  Pivot ]),   % Pivotより小さい値を抜いてきてソート
  Eq = [Pivot|[ Item || Item <- List, Item == Pivot ]], % Pivotと同じ値の配列。ListにはPivotが入っていないので足す。
  Gt = sort([ Item || Item <- List, Item >  Pivot ]),   % Pivotより大きい値を抜いてきてソート
  Lt ++ Eq ++ Gt. % 上の配列を連結した結果を返す。

実行結果は以下。期待通り動作しているっぽい。

36> sort:sort([3,3,6,7,8,9,1,4,5,2,3,7,1]).
[1,1,2,3,3,3,4,5,6,7,7,8,9]
37> sort:sort([3]).
[3]
38> sort:sort([3,3,4,3]).
[3,3,3,4]
39> sort:sort([3,3,4,3,7,1,3]).
[1,3,3,3,3,4,7]

Erlangのサンプル

ちなみにErlangのサンプルは次のような実装になっている。→Programming Examples - 3.2 Quick Sort

sort([Pivot|T]) ->
    sort([ X || X <- T, X < Pivot]) ++
    [Pivot] ++
    sort([ X || X <- T, X >= Pivot]);
sort([]) -> [].

なるほど、Pivotと同じ値の配列は集めなくてもよいわけですね。自作のヤツは無駄なスキャンが走ることになるのでやっぱダメっぽい。