Stabiliser la bibliothèque standard qsort?

Je suppose que la bonne vieille fonction qsort dans stdlib n’est pas stable, car la page de manuel ne dit rien à ce sujet. C’est la fonction dont je parle:

#include  void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); 

Je suppose que si je modifie ma fonction de comparaison pour inclure également l’adresse de celle que je compare, elle 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 id ) { return -1; } else if( pFooA->id > pFooB->id ) { return 1; } else if( pA  pA ) { return 1; } else { return 0; } } 

    Non, vous ne pouvez pas compter sur cela malheureusement. Supposons que vous ayez le tableau (deux champs dans chaque enregistrement utilisé pour la vérification mais uniquement le premier champ utilisé pour le sorting):

     BBBB,1 BBBB,2 AAAA,3 

    Quicksort peut comparer BBBB, 1 avec AAAA, 3 et les échanger, en donnant:

     AAAA,3 BBBB,2 BBBB,1 

    Si l’étape suivante consistait à comparer BBBB, 2 à BBBB, 1, les clés seraient identiques et, puisque BBBB, 2 a une adresse inférieure à BBBB, 1, aucun échange n’aura lieu. Pour un genre stable, vous devriez avoir fini avec:

     AAAA,3 BBBB,1 BBBB,2 

    La seule façon de le faire serait d’attacher l’adresse de départ du pointeur (pas son adresse actuelle ) et de sortinger à l’aide de celle-ci ainsi que des autres clés. De cette façon, l’adresse d’origine devient la partie mineure de la clé de sorting, de sorte que BBBB,1 finira par se retrouver avant BBBB,2 quel que soit l’emplacement des deux lignes de BBBB au cours du processus de sorting.

    La solution canonique consiste à créer (c’est-à-dire allouer de la mémoire pour 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 en revenant à la comparaison des valeurs de pointeur lorsqu’ils pointent être égaux. Cette approche présente l’avantage supplémentaire que vous ne modifiez pas du tout le tableau d’origine. Toutefois, si vous souhaitez que le tableau d’origine soit sortingé à la fin, vous devrez le permuter pour qu’il corresponde à l’ordre du tableau suivant. Retourne qsort .

    Cela ne fonctionne pas car, au cours de la procédure de sorting, l’ordre change et deux éléments n’auront pas une sortie uniforme. Ce que je fais pour rendre qsort stable à l’ancienne, c’est append l’index initial à l’intérieur de ma structure et initialiser cette valeur avant de la transmettre à 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); }