Decifrare il comportamento QSORT

Question

Ho bisogno della funzionalità di QSORT per il mio programma e finora non ha fatto il suo lavoro.

Sto essenzialmente ordinando una serie di valori di singoli carattere per raggrupparli in gruppi in modo da poter iterare attraverso l'array e determinare i conteggi per ciascun attributo. Il mio problema è che Qsort sta restituendo un array "ordinato" come

xxxxxbxbbbxfbxfbffffbxfxbbfbbbxxfxbxxfbbbbxbfxbxfbxbsxbbbxxbbxxffxbxfxfxbxxbxxfbbbfbxbbx
bbbsxfxbxbxxbfbfxbxxbxxbfxxbxsbfxxfxfxfffxbfxffbbfffsxsfbfbxbxbbbxxsbfbfbbbbbbxxfxfxffxf
xbxxbxfxbfbxbxxbxbxxbxbbffxxbxxffxxbxfxbxffxfsfxxfxxfxxfxfxxfxxbsxxbbbxsxxbbxxxbxfxsbxxx
ffbxfxxffbxxxfxxfxxfxfxxfffbxxxbxxxfffxsbbfffffxxxbbfxsbffxbxxfxbxxfbbfsbffsfffxfxfxbbffx
bxxfxbxxfxbbbfxxbbfxxbbbsxbxfbfbbxxbbfffxxfxxbbbfxxbxxxbbxxxbfxffxxxffxfxxffbxfsxbxxxfxfx
fsbbbxxxbfxfffsfxxxfssxxxfxfxxxxbxbbbxxbxxxxxxxxxxxxxxxxxxxfbfxxffxxbxxxxxxxsxsxxxxxxxxsxb
bxxxxxfxbxxxxfxxfxxxxxbbxfffbxbsxffbbbxsfbbfffbxbfbbxxbxxbbxxbffxfxxfxfbbxxbxfxxsfxxfxxbxf
xxbxxxbxbxbbxbbffxxxxbfbfxxxxxxfxffxxxxxxxxxxxxxxxxxxxxxbxffxbxbxbbxbbxxfbxfxbxxbxxbxbxxxb
xxbxbxbfbbffffffsbbxxbffbxfxxfxbfbfffsxbxxxsxxbbbbbxxxbxxxfxxfffxxxxxxxxxxxxxfxxbxxxxxxxxx
xxbfbxxxxxxxxxxxxxxxxxxxxxxxxxxbxbxxxxxfxxbxxxxffxbxxxxffxfbfffxbxxfxbfxbxxfxbxbfxxxxxfxbx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxsbxxxxffxfxxxxxxxxxfxfxxxbffffxxxfbxbxfxxxxxxxxxxxxxxxxxxxxf
fxfxbfxxxfxxxxx

Penso che il problema abbia a che fare con la mia chiamata o il metodo di confronto.

int compare(const void *a, const void *b){
  return *(char * const *) a - *(char * const *) b;
}

ed è usato in

qsort(temp, lineCount, sizeof(char), compare);

dove temp è l'array di personaggi sopra e lineCount è il numero di caratteri nell'array. Sia l'integrità dell'array che le dimensioni sono state verificate attraverso i test.

Qualsiasi aiuto è molto apprezzato.

Answer 1

char * const * è un puntatore a un puntatore a Char. Vuoi solo un puntatore da Char.

Provare:

int compare(const void *a, const void *b){
    return *(const char *) a - *(const char *) b;
}

Anche, sizeof(char) è sempre uguale a 1, per definizione. Quindi alcuni programmatori C non lo scriverebbero mai così. (È una questione di opinione se semplifica il codice più facile da leggere o solo segnali che non conosci davvero la lingua. Mi piace in questo caso, ma solo FYI.)

Answer 2

Almeno all'inizio, scrivo solo confronto un po 'più esplicitamente e riga per linea per il debug più facile:

int compare(const void *a, const void *b)
{
    char* alpha = (char*)a;   // Might get const-warning on these lines, ignore for now.
    char* beta  = (char*)b;

    if (*alpha == *beta) return 0;
    if (*alpha < *beta) return -1;
    return 1;
}

In questo modo, puoi guardarlo nel debugger più facilmente, aggiungere linee di uscita e generalmente abbattere il problema.

Una volta che funziona di nuovo, è possibile ricombarlo in un'unica linea di codice compatta.

Answer 3

Prova questo:

int compare(const void *a, const void *b){
  return *(const char *) a - *(const char *) b;
}

Ma imho, non hai bisogno qsort affatto!

Basta creare una tabella di int [256] (o forse meno) e iterare l'array per registrare il conteggio di ogni carattere:

int res[256];
memset(res, 0, 256*sizeof(int));
int i;
for (i=0;i<lineCount;i++){
    res[tmp[i]]++;
}

Ciò fornirebbe O (N) vs Qsort O (NLOGN).