いつでもクイックソートを使えば良いってもんじゃない

Posted on Saturday, September 13th, 2014 11:26:37

少し前に、クイックソートに関する記事を書きましたが、もう少し補足しておこうと思います。クイックだからって、いつでも使えば良いんじゃないよって話です。
参考:クイックソート

クイックソートを使うべきでないパターン

安定なソートを期待しているとき

クイックソートは安定なソートではありません。つまり、同じ値の要素の順序は保障されません。

処理に一定速度を期待するとき

クイックソートは、データに依存して処理速度が大幅に変動します。平均が O(n log n) なのに対して、最悪計算時間は O(n²) で、バブルソートの計算時間と同速度です。つまり速度が安定しないわけです。

メモリ容量が限られているとき

クイックソートは再帰呼び出しを用いているため、スタックを食い潰してしまいます。つまり、組み込み系等で、スタックサイズが小さい場合はクイックソートは向いていません。

まとめ

例えばC言語の場合、標準Cライブラリでサポートされているソート関数は stdlib.h の qsort 関数のみです。上記のような、クイックソートが不向きなパターンに出会った場合は、ヒープソートなりを自分で実装することを選択した方が好ましいでしょう。ではでは。

Share

  • このエントリーをはてなブックマークに追加
  • Pocket
  • 0 follow us in feedly

Your Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です