Haskellによるクイックソートのプログラム例

クイックソートによってリストをソートする Haskell プログラムの例。

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

配列の中から値 x (例:先頭の値) を一つ選び、x より小さい要素を配列の前半に集め、x 以上の要素を後半に集めます。前半と後半のそれぞれの配列について、同様の操作を繰り返します。

プログラム例 (1)

main = print $ qsort [0,5,9,7,2,6,1,4,8,3] 

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x : xs) = qsort lesser ++ [x] ++ qsort greater
  where
    lesser = filter (< x) xs
    greater= filter (>= x) xs

※ qsort :: (Ord a) => [a] -> [a] の部分は、この例の場合には qsort :: [Int] -> [Int] に差し替えても動作します。
※ qsort [] = [] を省略すると、実行時に Non-exhaustive patterns なるエラーが出る場合があります。

実行結果は以下のとおり。

[0,1,2,3,4,5,6,7,8,9]

プログラム例 (2)

リスト内包表記を使用。

main = print $ qsort [7,9,5,2,6,1,4,0,8,3] 

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x : xs) = qsort lesser ++ [x] ++ qsort greater
  where
    lesser = [ n | n <- xs, n < x ]
    greater = [ n | n <- xs, n >= x ]

実行結果はプログラム例 (1) と同じ。

参考 URL

HaskellWiki - Introduction - Quicksort in Haskell

参考資料

Haskell プログラミング ~純粋関数型言語への誘い~:プログラミングHaskell 訳者によるサポートページにある補足資料

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示