La estabilización de la qsort biblioteca estándar?

Question

Estoy asumiendo que la buena función qsort de edad en stdlib no es estable, ya que la página del manual 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?

Por ejemplo:

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 primer campo utilizado para la clasificación):

BBBB,1
BBBB,2
AAAA,3

Quicksort puede comparar BBBB, 1 con AAAA, 3 e intercambiarlos, dando:

AAAA,3
BBBB,2
BBBB,1

Si el siguiente paso fue comparar BBBB, 2 con BBBB, 1, las claves serían los mismos y, desde BBBB, 2 tiene una dirección menos de BBBB, 1, ningún intercambio se llevará a cabo. 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 el a partir de dirección del puntero (no su actuales dirección) y clasificar usando que, además de las otras teclas. De esa manera, la dirección original se convierte en la parte menor de la clave de ordenación de manera que BBBB,1 será finalmente terminan antes BBBB,2 independientemente de dónde van 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, usando un nivel extra de indirección y cayendo de nuevo a la comparación de puntero los valores cuando las cosas a los que apuntan son iguales. Este enfoque tiene el beneficio secundario potencial que no modifique la matriz original en todos - pero si desea que la matriz original que debe clasificarse en la final, que tendrá que permutar para que coincida con el orden de la matriz de punteros después retornos qsort.

Answer 3

Esto no funciona debido a que durante el procedimiento de clasificación, el orden cambiará y dos elementos no tendrá una salida consistente. Lo que hago para hacer un buen estable qsort pasada de moda es añadir el índice inicial dentro de mi estructura e inicializar este valor antes de pasarla 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);
}