標準ライブラリのqsortを安定？

StackOverflow https://stackoverflow.com/questions/584683

  •  06-09-2019
  •  | 
  •  

質問

私は、manページはそれについて何も言っていないため、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;
    }
}
役に立ちましたか？

解決

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

BBBB,1
BBBB,2
AAAA,3

クイックソートを与え、BBBB、AAAAと1,3を比較し、それらを交換することができる：

AAAA,3
BBBB,2
BBBB,1

は、次のステップは、BBBB、1でBBBB、2を比較した場合、キーはBBBBので、同一となり、2未満BBBB、1以上のアドレスを有し、全くスワップは行われません。安定したソートのために、あなたが終わっているはずます：

AAAA,3
BBBB,1
BBBB,2

それを行うための唯一の方法は、ポインタのの開始のアドレス（ないそのの現在ののアドレス）とソートそれだけでなく、他のキーを使用して添付することです。 BBBB,1は、最終的にかかわらず、2本のBBBB,2ラインがソート処理中にどこに行くのBBBB前になってしまいますように、その方法は、元のアドレスは、ソートキーのマイナーな一部となります。

他のヒント

カノニカル溶液は、間接の余分なレベルを使用して、ポインタの比較にフォールバック（即ちためのメモリを割り当て、塗りつぶし）元の配列の要素へのポインタの配列を、この新しい配列をqsort作ることである値の彼らが指すものは同じです。しかし、あなたは元の配列が最後にソートする場合は、あなたが後にポインタの配列順序を一致させるために、それを並べ替える必要があるでしょう - このアプローチは、あなたがすべてで元の配列を変更しない電位側の利益を持っていますqsort戻ります。

ソート手順の間、順序が変更されますので、これは動作しませんし、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);
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top