« Project Euler : Problem 16 ~ 整数のリスト化 | トップページ | Haskell で素数列 : 1000000 個目の素数が 3.5 秒で表示されました。 »

2010年3月 5日 (金)

Haskell でいろいろな「ソート」を考えてみた

 Haskell 関連の記事をネットで探していたら、ここここにソートに関する記事がありました。自分ならどうコーディングするかな?と思って、Haskell の練習のためにいろいろなソートを書いてみました。

 まずは、Haskell といえば「クイックソート」ですね。

import Data.List quickSort :: Ord a => [a] -> [a] quickSort [] = [] quickSort (x : xs) = quickSort as ++ [x] ++ quickSort bs where (as, bs) = partition (< x) xs
 ところがこのアルゴリズムは、リストの先頭の値をピボットにしているため、リストの大部分が既にソート済みの場合、極端にスピードが落ちます。
 そこで、リストの中央の位置にある値をピボットにするようにしてみました。
import Data.List quickSort :: Ord a => [a] -> [a] quickSort [] = [] quickSort ns = quickSort as' ++ [b] ++ quickSort bs' where (as, b : bs) = splitAt (div (length ns) 2) ns (as', bs') = partition (< b) (as ++ bs)
 こちらは完全にランダムなリストを与えた場合、前のコードより少し遅くなりますが、ソート済みのリストを与えてもまったく遅くなりません。

 次は「挿入ソート」を考えてみましょう……と思ったら、Haskell の Data.List モジュールにそのものずばり "insert" という関数がありました。

import Data.List insertionSort :: Ord a => [a] -> [a] insertionSort = foldr insert []
 おかげでこんなに簡単に書けてしまいました。

 アルゴリズム的に簡単と言われている「バブルソート」も考えてみました。
 このアルゴリズムは、隣り合う要素を入れ替える操作を頻繁に行うので、配列と繰り返しの組み合わせでは簡単にコーディングできます。例えば Ruby であれば次のようなコードになります。

# Ruby 版 バブルソート class Array def bubble_sort arr = Array.new(self) len = arr.size - 2 0.upto(len) do |i| 0.upto(len - i) do |j| arr[j], arr[j + 1] = arr[j + 1], arr[j] if arr[j] > arr[j + 1] end end return arr end end
 ところが Haskell では配列は使いにくいので、代わりにリストを使おうとすると結構面倒くさいことになりました。
bubbleSort :: Ord a => [a] -> [a] bubbleSort ns = iter ns [] [] True where iter (x1 : x2 : xs) tmp prd flag | x1 <= x2 = iter (x2 : xs) (x1 : tmp) prd flag | otherwise = iter (x1 : xs) (x2 : tmp) prd False iter [x] tmp prd flag | flag = reverse tmp ++ (x : prd) | otherwise = iter (reverse tmp) [] (x : prd) True iter [] _ prd _ = prd
 "reverse" を頻繁に使う割には結構速いかな?ネットで見つけた他のバブルソートよりは速いです(とはいえ、クイックソートとは比べ物にならないくらい遅いです)。
 結論としては、「バブルソートを Haskell でしてはいけない」ということでしょうか?

 続いては「マージソート」です。これは「クイックソート」と同じくらい速いです。

mergeSort :: Ord a => [a] -> [a] mergeSort xs = ms (length xs) xs where ms _ [] = [] ms _ [x] = [x] ms n xs = merge (ms m as) (ms (n - m) bs) where m = div n 2 (as, bs) = splitAt m xs merge xs [] = xs merge [] ys = ys merge xs@(x : xs') ys@(y : ys') | x <= y = x : merge xs' ys | otherwise = y : merge xs ys'

 

 

※追記 2010/11/25 : Ruby 版バブルソートのコードが、あまり Ruby っぽくなかったのと、破壊的なメソッドになっていたのが気に入らなかったので、書き換えました。

« Project Euler : Problem 16 ~ 整数のリスト化 | トップページ | Haskell で素数列 : 1000000 個目の素数が 3.5 秒で表示されました。 »

Haskell」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47728025

この記事へのトラックバック一覧です: Haskell でいろいろな「ソート」を考えてみた:

» 基数ソート [ツムジのひとりごと]
 こちらのブログを見て知ったのですが、「基数ソート」というソート法があるんですね。  面白そうだったので、 Wikipedia を参考に自分でもコードを書いてみました。(基本方針は、Wikipedia に従って、バケットソートと組み合せることにしました)  バケットソートに関して... [続きを読む]

» Haskellのクイックソートを紐解く [やじゅ@アプリケーション・ラボ わんくま支局]
Haskellのクイックソートを紐解く [続きを読む]

» Haskellのクイックソートを紐解く [やじゅ@アプリケーション・ラボ]
Haskellなどの関数型言語では、プログラムの簡潔さを表すのにクイックソートがよく使われます。 [続きを読む]

« Project Euler : Problem 16 ~ 整数のリスト化 | トップページ | Haskell で素数列 : 1000000 個目の素数が 3.5 秒で表示されました。 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ