Haskell ではクイックソートが簡単に実装出来ることで有名ですが、その アルゴリズムは実は C や Java での実装と違っていたりします。ここでは、 C や Java と同じアルゴリズムを用いた副作用版のクイックソートを実装して みましょう。もち、純粋関数型版より高速になります。
partition は副作用で as を変更するだけで
なく、戻り値として系列の分割位置を返します。ただし、戻り値は ST モナドに
包まれていますので、受け取るには(<-)演算子を使います。
unsafeSwap as i j は可変配列 as の i
番目の要素と j 番目の要素を入れ替えます。