クイックソートがセグフォる俺たち

クイックソート」は配列を順序に従って並べるソートと呼ばれるアルゴリズムの一種です。各ステップで配列をピボットと呼ばれる要素より大きい配列と小さい配列に分割し、それぞれの部分列に対して再帰的に実行することによって配列長nに対して、O(nlogn)という高速な処理を実現しています。

有名なアルゴリズムなので大抵のプログラミング言語にはクイックソートがライブラリとして提供されておりスクラッチから書く必要はないのですが、私はたまに手遊びで書くことがあります。

ただし、このアルゴリズム、「ピボットとの大小関係で分割して再帰的にかければいいんだな」くらいの雑な認識でいるとコーナーケースではまってセグフォったり正しくソートされないことがありますので、自分の備忘のためにいくつか注意点を列挙しておきたいと思います(以下では長さnの整数の配列を昇べきの順でソートすることを考えます)。

1. 先頭と末尾から配列を走査していくとき、スワップのために走査を止めるのはピボット「以下」とピボット「以上」のとき(「未満」と「以上」、「以下」と「超」ではいけない)。

  • 配列の先頭の要素がピボットより『大きい』にも関わらず、末尾からの走査でピボットよりも『小さい』要素が見つからないと、配列を二つに分けることができなくなります。例として(5, 4, 3, 6, 3)という配列を考えて、ピボットを'3'としたとき、先頭からの走査は最初の要素'5'で止まります。一方末尾からの走査の際、ピボット「未満」をスワップの基準とすると、末尾からの走査は先頭に至るまで停止せず配列は二つの部分列に分割されません。先頭と末尾を逆にしても同様です。
  • ピボット「以下」とピボット「以上」をスワップの基準とすると、ピボットに等しい要素がどちらの部分列に含まれるかが一義的には定まらなくなってしまう点が気になるが、最終的な結果には影響を与えない。

2. スワップした後は走査のインデックスを1進める。

  • 一度スワップした要素は二度とスワップする必要はなく、また単純に考えればそのようなことは起き得ないように思える。しかし上記のようにスワップの条件をピボット「以上」「以下」にしてしまうと、ピボットに等しい要素間のスワップが無限に繰り返される可能性があるため、スワップが行われた後は明示的に走査のインデックスを一つ進め、既にスワップが行われた要素を走査の対象から外す必要がある。

3.  再帰呼び出しする際の部分配列の境界に注意。

  • 先頭からの走査インデックスをiとしたとき、部分列への分割は0~i, (i+1)~(n-1) とするか、0~(i-1), i~(n-1) とするかわからなくなることがあります。ピボットより小さい、大きいことが保証されているのはどのインデックスまでかを注意する必要があります。

おそらくその他にも気をつけるべきことは多くあるのでしょうが、今日私が気がついたの以上の三点です。今後クイックソートをスクラッチから実装する際には気をつけていきたいと思います。

結論:素直にライブラリ使え。