メニュー  前へ  次へ

手続き脳によるHaskell -- シェルソート(shell sort)

 ここでは、Haskellでシェルソート(shell sort)を実装してみましょう。 シェルソートとはマルチ挿入ソートとでもいうべきソートです。 まず適当な間隔 h を決め、系列を h 飛ばしで 挿入ソート します。開始位置を一つずつずらしながら h 回の挿入ソートを行います。 そして h を少し小さくして同じことを h が 1 になるまで繰り返します。 h が 1 の場合は普通の挿入ソートを行ってソート終了です。

 h は \(h_0 = 1, h_{k+1} = 3h_k + 1\) の系列を、 ソートする系列の長さより小さい範囲で大きい方から使うと、 シェルソートの計算量はおよそ \(O(n^{1.25})\) になります。

 シェルソートの Haskell による実装は以下のようになります。

ShellSort1.hs

 さすがに、上記のコードだけでは 「普通にやれ、普通に!」 のスローガンに反しているような気がしますので、 それぞれの処理を解説しておきましょう。

 fst . break null . unfoldr (Just . splitAt h) というコードは、ソートする系列を h 間隔で刻んだリストを返します。 すなわち h = 2 だとすると、[1,2,3,4,5,6] を [[1,2],[3,4],[5,6]] というリストのリストに変換します。

 transpose は [[1,2],[3,4],[5,6]] を [[1,3,5],[2,4,6]] に変換します。そしてまた、[[1,3,5],[2,4,6]] を [[1,2],[3,4],[5,6]] に変換します。

 foldr insert [] は挿入ソートです。

 さて、これで一応シェルソートは出来ましたが、 実は上記のコードはメモリをバカ食いします。 原因は挿入ソートの foldr です。 Haskell を解説してあるページの中には、 foldl よりも foldr を推奨しているページとかもありますが、 メモリ効率で見るかぎり foldr は鬼門です。そこで、 メモリ効率の良い foldl に書き換えてみましょう。以下のようになります。

ShellSort2.hs

メニュー  前へ  次へ