Stabilisierung der Standardbibliothek qsort?

Question

Ich gehe davon aus, dass die gute alte qsort-Funktion in stdlib nicht stabil ist, weil die man-Seite nichts dazu sagt. 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 auch ändern, um die Adresse, dass beinhalten, die ich vergleiche, wird es stabil sein. Ist das korrekt?

ZB:

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, können Sie nicht auf dieser leider verlassen. Nehmen wir an, Sie das Array (zwei Felder in jedem Datensatz zur Überprüfung aber nur erste Feld verwendet für die Sortierung verwendet):

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, 2 mit BBBB, 1 zu vergleichen wäre, wären die Schlüssel gleich, und da BBBB, 2 eine Adresse kleiner als BBBB, 1 hat, findet kein Austausch statt.

AAAA,3 
BBBB,1 
BBBB,2 

der einzige Weg wäre es, zu tun, um die Start Adresse des Zeigers zu befestigen (nicht seine aktuelle-Adresse) und Art verwenden, wie: Für eine stabile Art, sollten Sie mit am Ende haben genauso wie die anderen Schlüssel. Auf diese Weise wird die ursprüngliche Adresse zum untergeordneten Teil des Sortierschlüssels, so dass BBBB,1 schließlich vor BBBB,2 enden wird, unabhängig davon, wo die zwei BBBB Zeilen während des Sortiervorgangs gehen.

Answer 2

Die kanonische Lösung besteht darin, ein Array von Zeigern zu den Elementen des ursprünglichen Arrays zu machen (dh Speicher zuzuweisen und zu füllen) und qsort dieses neue Array, das eine zusätzliche Indirektionsstufe verwendet und auf Zeiger Werte zurückfindet wenn die Dinge, auf die sie zeigen, gleich sind. Dieser Ansatz hat den potenziellen Nebeneffekt, dass Sie das ursprüngliche Array überhaupt nicht ändern. Wenn Sie jedoch möchten, dass das ursprüngliche Array am Ende sortiert wird, müssen Sie es so anpassen, dass es der Reihenfolge im Zeiger-Array entspricht qsort kehrt zurück.

Answer 3

Dies funktioniert nicht, da sich während des Sortiervorgangs die Reihenfolge ändert und zwei Elemente keine konsistente Ausgabe haben. Was ich mache, um gute altmodische qsort stabil zu machen, besteht darin, den initialen Index innerhalb meiner Struktur hinzuzufügen und diesen Wert vor der Übergabe an qsort zu initialisieren.

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); 
}