List comprehensionを使ったクイックソート
List comprehensionを使うと簡単にクイックソートができるらしい。というか、Programming Examplesにサンプルが載っているわけだけど、おもしろそうなので勉強がてら再発明してみた。
クイックソートのアルゴリズム
wikipediaより、クイックソートのアルゴリズムは次の通り。
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と同じ値の配列は集めなくてもよいわけですね。自作のヤツは無駄なスキャンが走ることになるのでやっぱダメっぽい。