La qsort de stabilisation bibliothèque standard?

Question

Je suppose que la bonne vieille fonction qsort dans stdlib n'est pas stable, parce que la page de l'homme ne dit rien à ce sujet. Ceci est la fonction dont je parle:

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

Je suppose que si je change ma fonction de comparaison pour inclure également l'adresse de ce que je compare, il sera stable. Est-ce exact?

Par exemple:

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

Non, vous ne pouvez pas compter sur cette malheureusement. Supposons que vous avez le tableau (deux champs de chaque enregistrement utilisé pour le contrôle, mais seulement le premier champ utilisé pour le tri):

BBBB,1
BBBB,2
AAAA,3

Quicksort peut comparer BBBB, 1 avec AAAA, 3 et de les échanger, donner:

AAAA,3
BBBB,2
BBBB,1

Si l'étape suivante était de comparer BBBB, 2 avec BBBB, 1, les clés seraient les mêmes et, depuis BBBB, 2 a une adresse moins BBBB, 1, aucun échange aura lieu. Pour une sorte stable, vous devriez avoir fini avec:

AAAA,3
BBBB,1
BBBB,2

La seule façon de le faire serait de fixer le à partir adresse du pointeur (pas son actuellement adresse) et trier par aussi bien que les autres touches. De cette façon, l'adresse d'origine devient la partie mineure de la clé de tri de sorte que BBBB,1 finira par se retrouver devant BBBB,2 quel que soit l'endroit où les deux lignes de BBBB vont au cours du processus de tri.

Answer 2

La solution canonique est de faire (par exemple allouer de la mémoire et remplir) un tableau de pointeurs vers les éléments du tableau d'origine, et qsort ce nouveau tableau, en utilisant un niveau supplémentaire d'indirection et de retomber à pointeur comparer valeurs quand les choses qu'ils pointent sont égaux. Cette approche a l'avantage de côté potentiel que vous ne modifiez pas le tableau original du tout - mais si vous voulez que le tableau original à trier à la fin, vous devrez permute pour correspondre à l'ordre dans le tableau de pointeurs après retourne qsort.

Answer 3

Cela ne fonctionne pas parce que pendant la procédure de tri, l'ordre changera et deux éléments ne sera pas avoir une production constante. Ce que je fais pour faire le bon vieux stable qsort est d'ajouter l'index initial dans ma struct et initialiser cette valeur avant de passer à 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);
}