Stabilizzare il qsort libreria standard?

Question

Sto assumendo che la buona funzione qsort vecchio in stdlib non è stabile, perché la pagina man non dice nulla al riguardo. Questa è la funzione di cui sto parlando:

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

Suppongo che se cambio funzione di confronto per includere anche l'indirizzo di quello che sto paragonando, sarà stabile. È corretto?

Esempio:

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

No, non si può fare affidamento su che purtroppo. Supponiamo di avere l'array (due campi in ogni record utilizzati per la verifica, ma solo il primo campo utilizzato per l'ordinamento):

BBBB,1
BBBB,2
AAAA,3

Quicksort può confrontare BBBB, 1 con AAAA, 3 e scambiarlo, dando:

AAAA,3
BBBB,2
BBBB,1

Se il passo successivo dovesse confrontare BBBB, 2 con BBBB, 1, le chiavi sarebbero la stessa cosa e, dal momento che BBBB, 2 ha un indirizzo meno di BBBB, 1, nessun scambio avrà luogo. Per un ordinamento stabile, si dovrebbe avere finito con:

AAAA,3
BBBB,1
BBBB,2

L'unico modo per farlo sarebbe quello di collegare il di partenza indirizzo del puntatore (non il suo corrente indirizzo) e ordinare usando che così come gli altri tasti. In questo modo, l'indirizzo originale diventa la parte minore della chiave di ordinamento in modo che BBBB,1 alla fine arriverà prima BBBB,2 indipendentemente da dove le due linee BBBB vanno durante il processo di ordinamento.

Answer 2

La soluzione canonica è rendere (cioè allocare memoria e compilare) una matrice di puntatori agli elementi della matrice originale e qsort questo nuovo array, utilizzando un ulteriore livello di riferimento indiretto e ricadere a confrontare puntatore i valori quando le cose a cui puntano sono uguali. Questo approccio ha il vantaggio collaterale potenziale che non si modifica la matrice originale a tutti - ma se si desidera che la matrice originale da ordinare, alla fine, dovrete permutare in modo che corrisponda l'ordine nella matrice di puntatori dopo qsort rendimenti.

Answer 3

Questo non funziona perché durante la procedura di ordinamento, l'ordinamento cambierà e due elementi non avrà output uniforme. Quello che faccio per fare un buon qsort stabile vecchio stile è quello di aggiungere l'indice iniziale dentro il mio struct e inizializzare tale valore prima di passarlo a 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);
}