比較を変更するだけでqsortが安定しますか？

Question

可能性の重複：
Stabilizing the standard library qsort?

それはちょうど私のコンプOPを変更することで、int型のためのqsort安定させることは可能ですか？それが私のコードです。私はこれを約5-7サイズの非常に小さな配列に使用しています。

static int compare(const void *a, const void *b) 
{ 
    const int A(*(const int*)(a)); 
    const int B(*(const int*)(b)); 

    return B - A; 
} 

Answer 1

C++を使用している場合、stable_sort関数は安定しており、O（nlogn）のパフォーマンスを持ちます。

それ以外の場合、インプレースクイックソートはその性質上、不安定です（私はそう信じています）。しかし、情報を格納するために余分な配列を使用する簡単な方法は安定しています。

かつて私は、私のマシン上の入力の場合についてqsort()とstable_sort()によって生成される結果が異なっていたことがわかったので、私は、不安定であるqsort()の少なくとも一つのバージョンを使用しました。

Answer 2

クイックソートなどの不安定なソートアルゴリズムを使用して比較演算子を変更するだけで安定させることはできません。安定したソートアルゴリズムを持つ開始を持っていなければなりません。そして、比較は重要ではありません（C++で厳密な弱い順序がある限り）。

Answer 3

並べ替える配列が実際にはそれほど小さい場合は、別の並べ替えアルゴリズムを使用する方がよい場合があります。例えば、答えはFast stable sort for small arrays (under 32 or 64 elements)とFast algorithm implementation to sort very small listです。