C：qsort関数の時間の複雑さは何ですか？

Question

Cの標準ライブラリのqsort関数の複雑さは？ 可能であれば、参考にもしてください。 C言語のマニュアルについては合理的に信頼できる情報源であるcppreference.comによると

#include <stdlib.h> 
    void qsort(void *base, size_t nmemb, size_t size, 
    int (*compar)(const void *, const void *)); 

Answer 1

、：名前にもかかわらず

、CやPOSIXどちらの規格は、クイックソートを使用して実装するために、この機能を必要とするか、またはいずれかを作ります複雑さまたは安定性の保証。

私は、次の程度qsort言うC ISO規格の原案、持っている：

のqsort関数はnmemb個のオブジェクトの配列、ベースによって指されたの初期の要素をソートします。各オブジェクトのサイズは、サイズによって指定されます。

配列の内容は、比較対象の 比較関数によって昇順にソートされます。比較対象は、比較される オブジェクトを指す2つの引数で呼び出されます。関数は、最初の引数がそれぞれ 以下または2番目の引数よりも大きいとみなされる場合は、0より大きい、より小さい整数、または を返します。

2つの要素が等しいと比較された場合、結果のソートされた配列の順序は不定です。

戻り値：

qsort関数は値を返しません。

これは、ここでの複雑さの保証について言及されていないので、リファレンスサイトが言うものをサポートします。

全体的に、ランタイムが平均で最悪の場合はO（n log n）になるとは想定できません。最悪の場合に退化するヒューリスティックを使用する実装の歴史があります。詳細については、「クイックソートのキラー敵」を検索してください。

最悪の場合、これはC++ std::sort,which is guaranteed to run in time O(n log n)と対照的です。