14/08/17 10:51:34.94 ruDVRpF3.net
こっちのクイックソートのほうが短くわかりやすかった。
クイックソート - NullPointer's Blog
Erlangで書くと…
quicksort([]) -> [];
quicksort([Head|Tail]) ->
quicksort([X || X <- Tail, X < Head ]) ++ [Head] ++ quicksort([X || X <- Tail, X >= Head]).
小さいのを左に集めて、大きいのを右に集めて、繰り返し…、アルゴリズムの説明そのままのコードになる。
簡単すぎ。アルゴリズムを理解するという目的であれば、関数型のコードの方が10000倍理解しやすい。
関数型っぽい書き方は、最近のJavaScriptならばサクッと書けますが…
function quickSort(array) {
if (array.length <= 1) return array;
var pivot = array.pop();
var lt = array.filter(function(a){ return a < pivot });
var ge = array.filter(function(a){ return a >= pivot });
return quickSort(lt).concat([pivot]).concat(quickSort(ge))
}
URLリンク(paulownia.hatenablog.com)