Haskellで選択ソート - かねぞうドロップ

Haskellのお勉強がてら簡単なソートアルゴリズムを実装してみる。

選択ソート

配列の中から最小の要素を探して、左側にぽいぽい置いていくアレ。通常の言語では配列を使って値をスワップしていく処理を書くことになるが、Haskellでは当然リストの状態を変更することなど許されない。ということで値をスワップせずに実現する必要がある。 ※最初に断っておくが、初心者が学習用に書いているもので何の最適化も施されていないし、コードが冗長であったり非効率であることはご愛嬌である。

問題を分割する

「困難は分割せよ」とは国語の教科書のルロイ修道士の発言。選択ソートは大きく分けて2つの処理からなっている。

最小値を発見する。
最小値の要素と、ソート済みでない要素の中で一番左にある要素を入れ替える。

Haskellでは2が素直に実装できないことはさておき、1の最小値を見つけるコードから書いていく。(あ、minimum関数の存在は知ってます。再帰のお勉強のために独自実装します。)

searchMin :: [Int] -> Int
searchMin (x:xs) = if length (x:xs) == 1
                   then x
                   else if  x > head xs
                     then searchMin xs
                     else searchMin (x:tail xs)

配列の要素を順に見ていく場合、他の言語ではイテレータを回すのが基本だが、Haskellでは再帰を使用する。ここでやっていることはリストの先頭の要素とその次の要素を比較。前者の方が大きければ前者を除いたリストをseachMinに渡す。後者の方が大きければ後者を除いたリストをsearchMinに渡す。これを繰り返していくと再帰が深くなるごとにsearchMinの引数として渡されるリストの要素数は減っていく。最終的に残った一つが最小値であるため、if式でリストの要素数が一つになったらそれを返すように書いている。

とりあえず関数を作ってテキトーなリストを渡してみる感じ上手くいっている。ヨシ！（現場猫感

さて、最小値を見つけるのは十分できる。鬼門は次だ。他の言語であれば最小値の要素の添字とソートが済んでいない要素の中で一番左の要素の添字(これはそのままイテレータの変数を使うのが普通)を取得して値をスワップすれば話は済む。しかし、Haskellではリストの値を文字通りスワップすることはできない。[1,2,3]を[3,2,1]にしたかったら[1,2,3]を変換した新しいリストを作る必要がある。

selectionSort :: [Int] -> [Int]
selectionSort (x:xs) = minNum:(selectionSort restArr)
  where minNum = searchMin (x:xs)
        restArr = delete minNum (x:xs)
selectionSort [] = []

ということでこんな感じになった。与えられたリストから最小値を見つける→その最小値を除いたリストを生成する→そのリストの最小値を見つけるを繰り返していく。効率はさておき、原理的にはしっかりと選択ソートになっているはず。ちなみに、一般的に選択ソートは安定ソートではないが、この実装だと安定ソートになる。 Wikipediaの安定ソートのページに載っている[1,2a,2b]の例だと、スワップを行うために2a,2bの順番が崩れてしまうが、この実装ではスワップを行わないため最小値として1が取り出された後の並びは[2a,2b]のようになり崩れていない。

高速化

もう少し高速化できないか探していたらこちらのブログを発見した。どうやらunfoldrを使った実装の方が早いらしい。せっかくなので自分のコードとの実行速度をtimeコマンドで比較してみた。ロジック自体の比較のため、独自実装したsearchMin関数はminimum関数に置き換えた。(ちなみに独自実装だと死ぬほど遅かった。)

テキトーに直積を使って30000個の数字からなるリストを作成し、ソートしてみる。

自分のコード

real    0m15.321s
user    0m15.241s
sys     0m0.080s

unfoldr仕様版

real    0m24.088s
user    0m24.077s
sys     0m0.010s

あれ、unfoldrを使わない方法実装の方が早かった。なんで？もしかしたらこの記事が書かれている頃のHaskellと現在のHaskellでは最適化の方法が異なるのかもしれない。原因をご存知の有識者の方がいらっしゃいましたらぜひともご教示お願いします。

それでは！