トップページ

手続き脳によるHaskell -- Sorting Algorithms

 このページは手続き脳から脱却出来ない筆者が、 Haskell で各種ソートアルゴリズムを実装してみた結果を紹介するページです。 ソートはアルゴリズムの基本ですから、 これで Haskell を攻略しようというわけです。

 ところで、Haskell に関するWebページを巡回していると、 高階関数やモナドなどを複雑に使ったアクロバチックでアブノーマルなコードに出会うことがしばしばあります。 書いている超頭の良い人達には簡単なのかもしれませんが、 頭の悪い私にはそんなコードは理解出来ません... orz。

 そこで私のページでは次のスローガンでプログラミングを行います。

 そんなわけで「モナドを理解したい」とか常人には不可能な無理難題を期待している人は他のページを当たってください。 筆者自身が分かってないので解説出来ません。ごめんなさい。

 また、アクロバチックでアブノーマルなコードを書く人は往々にして計算量のことを気にしていないようです。ようするに、 そういうコードは大抵遅いんです。そこで、もう一つスローガンを掲げます。

 それでは、以下のメニューからどうぞ。

  1. バブルソート
  2. シェイカーソート
  3. 選択ソート
  4. 挿入ソート
  5. コムソート
  6. シェルソート
  7. マージソート
  8. マージソート(ボトムアップ)
  9. クイックソート
  10. ヒープソート(完全2分木)
  11. ヒープソート(Leftist Heap)
  12. ヒープソート(Skew Heap)
  13. ヒープソート(Pairing Heap)
  14. バケットソート
  15. ツリーソート
  16. ツリーソート(赤黒木)
  17. ツリーソート(AVL木)
  18. ツリーソート(2-3木)
  19. ツリーソート(B木)
  20. 基数ソート
  21. 分布数えソート(計数ソート)

 さて、 上記のソートは清く正しい副作用を使わないスタイルで書かれています。でも、 Haskell には、ST モナドを使った副作用を用いるスタイルもあります。 以下のページでは、ST モナドを使った各種ソートの実装を紹介しています。 筆者はたいしてモナドを理解しているわけではありませんが、 興味のある方はご覧ください。でも、 副作用厳禁の良い子の Haskeller は見ちゃダメよ。

 バケットソートと基数ソートと分布数えソートの実装には、 Haskell の配列を使っています。しかし、 Haskell の入門書などでは配列のことを解説していないことが多いと思います。 そこで、簡単な配列の使い方に関するページを用意しました。 筆者も試行錯誤で配列の使い方を覚えたので、間違いがあるかもしれませんが、 何か参考資料は無いのかとお探しの方はご覧ください。