標準ライブラリqsortを安定化しますか？

Question

私は、stdlibの古いqsort関数が安定していないと仮定しています。なぜなら、マニュアルページはそれについて何も言わないからです。これは私が話している機能である：

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

私は私が私の比較関数を変更した場合も、私は比較てるもののアドレスが含まれるようにすることを想定し、それが安定します。あれは正しいですか？

例：

int compareFoos(const void* pA, const void *pB) { 
    Foo *pFooA = (Foo*) pA; 
    Foo *pFooB = (Foo*) pB; 

    if(pFooA->id < pFooB->id) { 
     return -1; 
    } else if(pFooA->id > pFooB->id) { 
     return 1; 
    } else if(pA < pB) { 
     return -1;    
    } else if(pB > pA) { 
     return 1; 
    } else { 
     return 0; 
    } 
} 

Answer 1

いいえ、あなたは、残念ながらそれに頼ることはできません。あなたは、アレイ（2つのチェックするために使用される各レコードのフィールドが、ソートに使用される唯一の最初のフィールド）を持っていると仮定しましょう：

BBBB,1 
BBBB,2 
AAAA,3 

クイックソートは、AAAAとBBBB、1 3を比較し、それらを交換、与えることがあります。

AAAA,3 
BBBB,2 
BBBB,1 

BBBB、2をBBBB、1と比較すると、キーは同じになり、BBBB、2のアドレスはBBBB、1より小さいため、スワップは行われません。それはポインタ（ないその現在アドレス）の開始アドレスを添付することです行うと、ソートなどのことを使用する

AAAA,3 
BBBB,1 
BBBB,2 

唯一の方法：安定したソートのために、あなたが終わっているはずです他のキーと同じように。このようにして、元のアドレスはソートキーのマイナー部分になるので、ソート処理中にBBBB行がどこに行くかにかかわらず、は最終的にBBBB,2の前になります。

Answer 2

標準的な解決策は、元の配列の要素へのポインタの配列を作成する（つまり、メモリを割り当てる）ことであり、qsortはこの新しい配列を追加レベルの間接参照を使用してポインタ彼らが指しているものが等しい場合。この方法は、元の配列をまったく変更しないという潜在的な副次的な利点がありますが、元の配列を最後にソートする場合は、後でポインタの配列内の順序と一致するように配列を並べ替える必要がありますqsortが返されます。

Answer 3

ソート処理中に順序が変わり、2つの要素の出力が一貫しないため、これは機能しません。私が昔ながらのqsortを安定させるために行うことは、構造体内に初期インデックスを追加し、その値をqsortに渡す前に初期化することです。

typedef struct __bundle { 
    data_t some_data; 
    int sort_score; 
    size_t init_idx; 
} bundle_t; 

/* 
. 
. 
. 
. 
*/ 

int bundle_cmp(void *ptr1, void *ptr2) { 
    bundle_t *b1, *b2; 
    b1 = (budnel_t *) ptr1; 
    b2 = (budnel_t *) ptr2; 
    if (b1->sort_score < b2->sort_score) { 
     return -1; 
    } 
    if (b1->sort_score > b2->sort_score) { 
     return 1; 
    } 
    if (b1->init_idx < b2->init_idx) { 
     return -1; 
    } 
    if (b1->init_idx > b2->init_idx) { 
     return 1; 
    } 
    return 0; 
} 

void sort_bundle_arr(bundle_t *b, size_t sz) { 
    size_t i; 
    for (i = 0; i < sz; i++) { 
     b[i]->init_idx = i; 
    } 
    qsort(b, sz, sizeof(bundle_t), bundle_cmp); 
}