真・バブルソート

Program

ここで書いたバブルソート(偽)はアルゴリズムじゃなくて、引き起こされる結果の特徴的な部分から考えた。
思考の順序としては、

  1. バブルソートは一番後ろから確定していくよなー
  2. なら最大値を一番後ろにくっつけて、それ以外をまた同じソートにかければいっか

で、出来上がったのが実は選択ソートでした、という。


バブルソートは、隣り合った要素を比較していって、前の要素が後ろの要素よりも大きかった場合に交換するので、結果後ろから確定していくものの、それは最大値を選んでいるわけではない。


ということで、リベンジ。

bblSort [] = []
bblSort xs = (bblSort $ reverse $ tail reversed) ++ [head reversed]
  where
    reversed = reverse $ bbl xs
    bbl [x] = [x]
    bbl (x:y:xs) = if x > y then y : (bbl $ x:xs)
                            else x : (bbl $ y:xs)

target = [5, 2, 4, 6, 3, 1, 0]

main = print $ bblSort target


うーん、let使った方がいいのか？

bblSort [] = []
bblSort xs = let bbl [x] = [x]
                 bbl (x:y:xs) = if x > y then y : (bbl $ x:xs)
                                         else x : (bbl $ y:xs)
                 reversed = reverse $ bbl xs
             in (bblSort $ reverse $ tail reversed) ++ [head reversed]


順番としてはこっちの方がみやすいな。


if-then-elseよりガードの方がわかりやすい？

bblSort [] = []
bblSort xs = let bbl [x] = [x]
                 bbl (x:y:xs) | x > y     = y : (bbl $ x:xs)
                              | otherwise = x : (bbl $ y:xs)
                 reversed = reverse $ bbl xs
             in (bblSort $ reverse $ tail reversed) ++ [head reversed]


(:)はリスト側が長いと読みにくい気がするから(++)にかえてみる。

bblSort [] = []
bblSort xs = let bbl [x] = [x]
                 bbl (x:y:xs) | x > y     = [y] ++ (bbl $ x:xs)
                              | otherwise = [x] ++ (bbl $ y:xs)
                 reversed = reverse $ bbl xs
             in (bblSort $ reverse $ tail reversed) ++ [head reversed]


とりあえずこんな感じで。