Estabilizar a qsort biblioteca padrão?

Question

Estou assumindo que a boa função qsort velho no stdlib não é estável, porque a página homem não dizer nada sobre isso. Esta é a função que estou falando:

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

Eu assumo que se eu mudar de função de comparação para incluir também o endereço do que estou comparando, será estável. Isso está correto?

Por exemplo:

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

Não, você não pode confiar em que, infelizmente. Vamos supor que você tem a matriz (dois campos em cada registro usado para a verificação, mas apenas o primeiro campo usado para classificar):

BBBB,1
BBBB,2
AAAA,3

Quicksort pode comparar BBBB, 1 com AAAA, 3 e trocá-los, dando-:

AAAA,3
BBBB,2
BBBB,1

Se o passo seguinte foi comparar BBBB, 2 com BBBB, 1, as chaves seria o mesmo e, uma vez BBBB, 2 tem um endereço menos de BBBB, 1, nenhuma troca ocorrerá. Para uma espécie estável, você deve ter acabado com:

AAAA,3
BBBB,1
BBBB,2

A única maneira de fazer isso seria para anexar o começando endereço do ponteiro (não a sua atual endereço) e classificar usando que, assim como as outras chaves. Dessa forma, o endereço original se torna a parte menor da chave de ordenação para que BBBB,1 acabará antes BBBB,2 independentemente de onde as duas linhas BBBB ir durante o processo de triagem.

Answer 2

A solução canônica é fazer (ou seja, alocar memória para e preenchimento) uma matriz de ponteiros para os elementos da matriz original, e qsort esta nova matriz, usando um nível extra de engano e caindo de volta para comparar ponteiro valores quando as coisas apontam para são iguais. Esta abordagem tem o benefício colateral potencial que você não modificar a matriz original em tudo - mas se você quiser a matriz original a serem classificados no final, você terá que permutar-lo para corresponder a ordem na matriz de ponteiros depois qsort retornos.

Answer 3

Esta não funciona porque durante o procedimento de classificação, a ordem vai mudar e dois elementos não terá saída consistente. O que eu faço para fazer um bom estável qsort old-fashioned é adicionar o índice inicial dentro de minha struct e inicializar esse valor antes de passá-lo para 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);
}