Haskellなどの関数型言語では、プログラムの簡潔さを表すのにクイックソートがよく使われます。
Haskellによるクイックソートは下記の構文になります。
qsort [] = []
qsort (p:xs) = qsort smaller ++ [p] ++ qsort larger
where
smaller = [x | x <- xs, x < p]
larger = [x | x <- xs, x >= p]
この構文を見ただけでは、Haskellを知らない人にはピンとこないと思います。
今回Haskellについては特段の説明はしませんが、一応、静岡Developes勉強会の昨年（2010）のテーマが「Haskell読書会」でした。
その時に、私が初回の講師として作成した資料を提示しておきます。
Haskellのクイックソートの構文について、簡単に説明します。
・再帰を使用しております。
・「++」はリストの連結演算子です。例 [1,2,3] ++ [4,5] -> [1,2,3,4,5]
・[x | x <- xs, x < p]と[x | x <- xs, x >= p]は、リスト内包表記を使用しています。
リスト内包表記は、パッと見ると分かりにくいですが、使い方が分かるとすごく便利です。
PythonやHaskellやErlang等で採用されています。残念ながらRubyにはまだありません。
例
[x | x <- [1..10]] とした場合、[1,2,3,4,5,6,7,8,9,10] がxに返されます。
[x | x <- [1..10], even x]とした場合、[2,4,6,8,10] がxに返されます。カンマの後のeven xは、フィルタの条件で偶数を判定しています。
[x | x <- [1..10], even x, x > 5]とした場合、[6,8,10]がxに返されます。複数のフィルタ条件をカンマ区切りで続けて記述できます。
リスト内包表記を使って1から5の二乗の和を計算する式
sum' = sum[x^2 | x <- [1..5]]とした場合、[1,4,9,16,25]が返されます。
実はリスト内包表記は数学の集合記法(set notation)をコード化したものなのだそうです。
「<-」という記号は、a∈A（aはAの要素なり）の形を真似たものです。
・where節は、"ここで" という意味の予約語で、前の行で出てきた変数の smaller と larger を定義します。
SQLを使用していたりすると、whereを見ると条件を書くのかと混乱します。(今回はたまたま条件を書いてますね)
ちなみに、where節は使わないで記述すると１行に纏めることが出来ます。
qsort (p:xs) = qsort [x | x <- xs, x < p] ++ [p] ++ qsort [x | x <- xs, x >= p]
クイックソートは、ピボットと呼ぶ軸となる要素の値より大きい要素群、小さい要素群という具合にソートの対象となる部分を小さくしてゆきながら全体のソートを完了させるアルゴリズムです。
ピボットは、一般的にはデータの総数の中央値が望ましいですが、今回のHaskellによるクイックソートでは先頭をピボットとしてします。
先頭以外のピボットにしたHaskellによるクイックソートは下記サイトを参照してください。
http://tsumuji.cocolog-nifty.com/tsumuji/2010/03/haskell-9840.html
http://techtipshoge.blogspot.com/2011/06/haskell3.html
クイックソートでソートされていく様子が下図となります。
赤丸が軸要素(ピボット)で、赤丸の値より小さい要素群と大きい要素群に段階的に分けていくとソートが完了します。
Haskellで、実際にソートしていく様子を展開していきます。
その前に、要素が1つになった場合、qsort [x] = [x] となります。qsort[2]では次の展開時は、[2]と表現します。
qsort [x]
= qsort(x:[])
qsortを適用
= qsort [] ++ [x] ++ qsort []
qsortを適用
= [] ++ [x] ++ []
++ を適用
= [x]
一番最初のピボットを青字、それ以降のピボットを赤字にしています。
qsort [3,2,0,5,8,3,4,1,3,2]
qsortを適用
= qsort[2,2,0,1] ++ [3] ++ qsort[8,3,4,5,3]
qsortを適用
= (qsort [0,1] ++ [2] ++ qsort[2]) ++ [3] ++ (qsort [3,4,5,3] ++ [8] ++ qsort[])
qsortを適用
= ((qsort [] ++ [0] ++ [1]) ++ [2] ++ [2]) ++ [3] ++ ((qsort [] ++ [3] ++ qsort[4,5,3]) ++ [8] ++ [])
qsortを適用
= ([] ++ [0] ++ [1] ++ [2] ++ [2]) ++ [3] ++ ([] ++ [3] ++ (qsort [3] ++ [4] ++ [5]) ++ [8] ++ [])
qsortを適用
= [0,1,2,2] ++ [3] ++ ([3] ++ [3] ++ [4,5]) ++ [8]
++ を適用
= [0,1,2,2] ++ [3] ++ [3,3,4,5] ++ [8]
++ を適用
= [0,1,2,2] ++ [3] ++ [3,3,4,5,8]
++ を適用
= [0,1,2,2,3,3,3,4,5,8]