[迷信] データ列のソートには qsort 関数を使うべし

ソートのアルゴリズムにはいろいろありますが、中でもクイックソートは比較的高速なアルゴリズムです。その名前からも分かるように、qsort 関数はクイックソートの実装であることを示唆しています。実際には、規格上は qsort 関数にクイックソートを用いて実装することが要求されているわけではないので何でもよいのですが、多くの場合はクイックソートを用いていると考えられます。

標準Cライブラリでは、ソートのための関数は qsort 関数しかないため、qsort 関数は最も手軽に使用できるソート方法です。しかし、いくつかの状況では、qsort 関数は使えませんし、使えたとしても好ましくありません。以下に、qsort 関数を使うべきでは状況を挙げてみます。

qsort 関数が使えない状況

データ列が配列ではない場合

qsort 関数はデータ列が配列であることを前提としています。線形リストであったり、ファイル上のデータであったりする場合には使えません。いったん配列に読み込んでから qsort でソートし、書き戻すことは可能ですが、多くの場合メリットがありません。マージソートなど、データ構造や格納方法に適した他の方法を用いて、ソートを自作する方がよいでしょう。なお、C++の std::list の場合、メンバ関数 sort を利用できます。

安定なソートが必要な場合

クイックソートは安定ではありません。すなわち、比較して値が等しい要素がどの順序になるかは不定です。比較して値が等しい要素が元の順序を保つ必要がある場合には不適切です。C++では、安定ソートには std::stable_sort 関数テンプレートを利用することができます。

スタックが小さい場合

クイックソートは多くの場合、再帰呼出しを用いて実装されます。あるいは、再帰を用いない場合はあらかじめ大きな配列を自動変数として確保します。ローエンドの組込み機器など、スタックサイズの制限が厳しい環境では、ヒープソートなど、他の方法を選択する方が適しています。処理系がそのことを配慮して qsort 関数を実装している場合は問題ありませんが、その場合でも移植を行う場合は要注意です。

フリースタンディング環境の場合

フリースタンディング環境では qsort 関数がサポートされません。処理系によっては提供されていることもありますが、移植性を考慮するなら使用すべきではないでしょう。

qsort 関数が好ましくない状況

計算時間を予測したい場合

リアルタイム性が要求される状況など、計算時間を予測したい場合には、データに依存して計算時間が大幅に変化するクイックソートは不向きです。クイックソートの計算時間は、平均的には O(n log n) ですが、最悪計算時間は O(n2) であり、これはバブルソートの計算時間と同じです。リアルタイム性を保証するには、最悪計算時間に合わせるしかないため、クイックソートの利用は好ましくありません。ヒープソートなどを用いて自作すべきでしょう。

C++の場合

C++では、実装にもよりますが、qsort 関数より std::sort 関数テンプレートを用いる方が圧倒的に高速です。qsort は比較関数のコールバックがかなり大きなオーバーヘッドになります。一方、C++の std::sort では、比較に関数オブジェクトを使えますので、結果としてインライン置換することが可能になります。

また、配列の要素が C 互換型（POD 型）であればよいのですが、そうでなければ、qsort 関数を使うと不具合につながります。なぜなら、qsort 関数では、要素の交換を単なるメモリブロックの交換として行っているだけであり、適切な swap 関数を用いたり、コピーコンストラクタを呼び出したり、といったことは一切ないからです。

実は、今回「データ列のソートには qsort 関数を使うべし」を迷信として採り上げたのは、 C++ の場合に関しての理解不足をよく見かけるからです。先に挙げた（C++ 以外の）状況で qsort 関数を使うべきでないことは、少し経験を積んだプログラマであれば容易に判断がつきます。しかし、単に C++ になっただけの場合には、つい std::sort ではなく qsort を使ってしまうものです。