Die Stabilisierung der Standardbibliothek qsort?

Question

Ich gehe davon aus, dass die gute alte qsort Funktion in stdlib nicht stabil ist, weil der Mann Seite sagt nichts darüber. Dies ist die Funktion ich spreche:

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

Ich gehe davon aus, dass, wenn ich meine Vergleichsfunktion ändern, umfassen auch die Adresse von dem, was ich zu vergleichen, wird es stabil sein. Ist das korrekt?

Beispiel:

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

Nein, Sie können nicht auf diese leider verlassen. Nehmen wir an, Sie das Array (zwei Felder in jedem Datensatz verwendet für die Überprüfung aber nur erste Feld verwendet für die Sortierung):

BBBB,1
BBBB,2
AAAA,3

Quicksort kann vergleichen BBBB, 1 mit AAAA, 3 und tauschen sie, geben:

AAAA,3
BBBB,2
BBBB,1

Wenn der nächste Schritt BBBB vergleichen waren, 2 mit BBBB, 1, wären die Schlüssel gleich und, da BBBB, 2 hat eine Adresse kleiner als BBBB, 1, wird kein Swap statt. Für eine stabile Art, haben Sie Folgendes am Ende mit:

AAAA,3
BBBB,1
BBBB,2

Der einzige Weg, es zu tun wäre, die Start Adresse des Zeigers zu befestigen (nicht seine Strom Adresse) und Art verwenden, sowie die anderen Tasten. Auf diese Weise, die ursprüngliche Adresse wird zum kleineren Teil des Sortierschlüssel, so dass BBBB,1 schließlich vor BBBB,2 am Ende, unabhängig davon, wo sich die beiden BBBB Linien während des Sortierprozesses gehen.

Answer 2

Die kanonische Lösung zu machen (dh weisen Speicher für und füllt) ein Array von Zeigern auf die Elemente des ursprünglichen Arrays und qsort diese neue Anordnung, ein extra Dereferenzierungsebene Verwendung und zurück zum Vergleich Zeiger falling Werte , wenn die Dinge, die sie gleich zeigen. Dieser Ansatz hat den möglichen Neben Vorteil, dass Sie gar nicht das ursprüngliche Array ändern - aber wenn Sie die Original-Array wollen am Ende sortiert werden, werden Sie es permutieren haben die Reihenfolge, in der Array von Zeigern entsprechen nach qsort kehrt zurück.

Answer 3

Das funktioniert nicht, weil während des Sortiervorganges wird die Reihenfolge ändern und zwei Elemente nicht konsistent ausgegeben haben. Was ich tue, gute altmodischen qsort stabil zu machen, ist der anfänglichen Index in meinem struct hinzufügen und diesen Wert initialisieren, bevor er es 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);
}