ここでは、 Haskell でシェイカーソート(shaker sort)を実装してみましょう。 シェイカーソートは双方向バブルソートとでも言うべきソートです。 バブルソート が要素の比較・交換を一方向で行うのに対して、シェイカーソートでは、 系列を添字が増える方向にバブルソートした後、 添字の減る方向にもバブルソートします。 Haskell によるシェイカーソートの実装は以下のようになります。
この実装では、 要素の交換が行われなくなった場合に、 ループ(再帰)を終了するようになっています。それを実現しているのが swapped 変数です。swapped 変数は要素の交換が行われると True に書き換えられます。 Haskell では原則的には変数は書き換え出来ませんが、 再帰呼び出しの引数にすれば書き換えられます。 バブルソートのページでは戻り値を使って変数の書き換えを実現しましたが、 こちらは、 再帰が深くなっていく方向で変数を書き換えたい場合のテクニックです。
さて、何とかシェイカーソートを Haskell で実装できていますが、 どうも美しくありません。 試しに C++ でシェイカーソートを実装してみましょう。 以下のようになります。
美しい！行きと帰りのバブルソートが対称なコードになっています。 どうもシェイカーソートは Haskell 向きではないようです。しかし、 Haskell によるシェイカーソートは、 ソートする要素数が少ない場合に高速になります。 少ない要素を Haskell でソートしなければならない人は憶えておいて損はないでしょう。