Go遊会 4日目 （追記あり）

※追記あり

今日のテーマ：クイックソート

クイックソートは昔から一発で書けた試しがない。 今回も例によって10分くらいで最初の大筋は書き終わったけど、細かい境界条件バグにハマって35分くらいかかった。

はまっていた原因はピボット値の選択方法をサボったこと。 ピボット値を選ぶ際に、適当（配列の中央とか）から1個だけ値を取ってくると、その値がたまたま最小値 or 最大値のときに配列を分割できなくなるので、結果無限再帰となる。 3個以上の配列の場合には、3個値をサンプリングして中央値をピボットとして選択することでこのケースは回避できる。

次回のテーマ：ヒープソート

バイナリヒープは今まで何度も実装してるし単純なので10分くらいでサクッと終わらせたい。

その後は、基数ソート系、トライとか？ あるいは、二分探索木による集合、平衡木への拡張とか。 この関係の Introduction to Algorithms の演習問題をやるとかでもよいかもしれない。

追記：アルゴリズムの勘違いを修正

FacebookでShiroさんからピボットの選び方に関わらず無限再帰はしないはずでは、とご指摘を頂く。 改めてクイックソートのアルゴリズムを確認しなおすと、↑で実装していたものは少々間違っていることに気がついた。 ↑の実装では、「ピボットの値以下」「ピボットの値より大きい」の条件を満たすように配列を分割することだけを考えていて、ピボットの要素はswapせずに放置されるようになっていた。そのため、ピボットの値として配列内の最大値が選択されたときには、配列が分割されずに無限再帰してしまっていた。 本来のクイックソートのアルゴリズムでは、ピボットとして選択した要素が、配列を分割する境界に移動するようにswapを繰り返してゆくので、ピボットの要素を除いた部分に対して再帰することができ、無限に再帰しないことが保証できる。 この方法に修正したところ、ピボットの選び方によらずちゃんと動作するようになった。