ここでは、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 による実装は以下のようになります。
さすがに、上記のコードだけでは 「普通にやれ、普通に！」 のスローガンに反しているような気がしますので、 それぞれの処理を解説しておきましょう。
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 に書き換えてみましょう。以下のようになります。