Estabilizando la biblioteca estándar qsort?

Question

Supongo que la buena función qsort anterior en stdlib no es estable, porque la página man no dice nada al respecto. Esta es la función que estoy hablando:

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

Asumo que si cambio de función de comparación para incluir también la dirección de lo que estoy comparando, será estable. ¿Es eso correcto?

Ej:

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, no se puede confiar en que, por desgracia. Supongamos que usted tiene la matriz (dos campos de cada registro utilizadas para el control, pero sólo el primer campo que se utiliza para clasificar):

BBBB,1 
BBBB,2 
AAAA,3 

ordenación rápida puede comparar BBBB, 1 con AAAA, 3 e intercambiarlos, dando:

AAAA,3 
BBBB,2 
BBBB,1 

Si el siguiente paso fuera comparar BBBB, 2 con BBBB, 1, las claves serían las mismas y, dado que BBBB, 2 tiene una dirección inferior a BBBB, 1, no se realizará ningún cambio. Por una especie estable, que debería haber terminado con:

AAAA,3 
BBBB,1 
BBBB,2 

La única manera de hacerlo sería para fijar la dirección a partir del puntero (no su actual dirección) y el uso de una especie que a medida así como las otras llaves. De esta forma, la dirección original se convierte en la parte menor de la clave de clasificación, de modo que BBBB,1 eventualmente terminará antes de BBBB,2 independientemente de dónde vayan las dos líneas BBBB durante el proceso de clasificación.

Answer 2

La solución canónica es hacer (es decir, asignar memoria para y rellenar) una matriz de punteros a los elementos de la matriz original, y qsort esta nueva matriz, utilizando un nivel extra de indirección y volver a caer a la comparación de puntero valores cuando las cosas que señalan son iguales. Este enfoque tiene el beneficio potencial potencial de no modificar en absoluto la matriz original, pero si desea que la matriz original se ordene al final, tendrá que permutarla para que coincida con el orden en la matriz de punteros después de qsort regresa.

Answer 3

Esto no funciona porque durante el procedimiento de clasificación, el orden cambiará y dos elementos no tendrán una salida consistente. Lo que hago para hacer estable el antiguo qsort es agregar el índice inicial dentro de mi estructura e inicializar ese valor antes de pasarlo 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); 
}