qsort/クイックソートについて

構造体の配列をqsortで昇順に並び替えるプログラムを作成しています。
対象は数値項目で、単純にNo順に並び替えるイメージです。

クイックソートは、配列の内容によって処理時間が変わると聞いたので、一番遅くなる場合の時間を調べたいのですが、どのような並びだと一番遅くなるのでしょうか？

No.3 ベストアンサー 回答者： chie65535 回答日時： 2009/04/03 16:21

「値が等差数列で、並べたい順番と真逆に並んでいる時」が最悪と言われています。

例えば
８、７、６、５、４、３、２、１
を
１、２、３、４、５、６、７、８
に並べ替える場合など。

但し、ライブラリのqsortは「要素数がある程度少なくなった場合、アルゴリズムをクイックソート以外の物に切り換える場合がある」ので、クイックソートの計算量を検証する場合は「ソートルーチンを自作」しないと、正確な数値は計れません。

No.5 回答者： Tacosan 回答日時： 2009/04/05 00:18

当然ですが, ひとえにクイックソートといっても「実際にどのようにピボットを決めているのか」がわからないと「どのような並びで最悪になるのか」はわかりません.

でも, いくらなんでも「列の最初 (または最後) をピボットにするクイックソート」は「しょぼい」と言われてもしかたがないと思う.
もちろん deterministic なクイックソートではどんな (O(1) の) ピボットの決め方をしてもそれに対応して「(O(n^2) かかる) 最悪の場合」は存在します. ですが, 列の端の要素をピボットにすると「昇順または降順にソートされた列」が最悪になるので普通はそんな風にしないと思います. 例えば「列の中央にあるデータ」とか「最初のデータ, 最後のデータと中央のデータの中央値」ってやればこれほど簡単ではないので, そのようなピボットの決め方の方が普通じゃないでしょうか.

No.4 回答者： jacta 回答日時： 2009/04/04 17:06

処理系を特定しなければどうしようもありません。

すでに回答が出ているように、qsortはクイックソートで実装されているとは限りません。スタックが小さい環境ではヒープソート等で実装するのがよいでしょうし、そうでない場合でも、イントロソートの方が普通は優れています。
どんなアルゴリズムでどのように実装されているかで、かなり変わるはずです。

No.2 回答者： Tacosan 回答日時： 2009/04/03 00:54

えぇと, そもそも「qsort がクイックソートをする」って決まってるわけじゃないですけど....

規格上は「ソートする」としか書いてないですし.

No.1 回答者： ymmasayan 回答日時： 2009/04/02 23:45

クイックソートにも色々なアルゴリズムが有りますが

一般的には降順に並んでいるデータを昇順に並べ替えるのが一番時間がかかるとされています。
理由は最初に出てきたデータをピボット(グループ分割のための基準データ）にするためです。
降順だと最後まで「１:残り」にしか分割されません。
平均的には２分割の繰り返しだと「クイック」になるのですが。