C'è una buona libreria per ordinare una vasta gamma di numeri in C?

Question

Se ho una vasta gamma di numeri interi o galleggianti, quello che è un buon algoritmo / implementazione per l'ordinamento (in C)?

E 'un po' tardi nel gioco per una modifica ... ma cerco di correttezza e velocità .

Answer 1

Per l'ordinamento array di numeri, si consideri un algoritmo radix sort. Se correttamente progettato, questo tipo dovrebbero fornire prestazioni migliori rispetto GLIBC qsort ().

La libreria usort contiene implementazioni di tipo specifico per tutti i principali tipi numerici C.

http://bitbucket.org/ais/usort/wiki/Home

Il vantaggio della velocità di radix sort sopra GLIBC qsort è circa 2,5 volte per la doppia precisione numeri in virgola mobile a N = 1000000 sul mio portatile Intel a 64 bit. Tuttavia, come N cresce il vantaggio dovrebbe essere ancora maggiore in quanto ordinamento digitale è un algoritmo tempo lineare richiedendo numero costante di passaggi attraverso i dati.

Per molto piccola N, lo stesso codice invia ad un introsort o inserzione.

Answer 2

qsort () della libreria standard è un good'un.

Le funzioni di confronto sarebbe banale per questi casi:

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(EDIT:. La versione di questi sulla base della differenza b da una si basa sul comportamento di overflow firmato, quindi non è una buona idea)

Answer 3

Non è mai una cattiva idea di utilizzare qsort ... a meno che non si sa qualcosa circa i numeri.

Hai contrassegnati con radix sort. Quanta memoria è disposto a investire? Sono i numeri all'interno di un intervallo specifico? Hanno proprietà che rende ordinamento digitale fattibile?

A meno che non si desidera utilizzare un sacco di memoria, qsort è una grande opzione.

Answer 4

Dato un enorme quantità di RAM che stiamo ottenendo al giorno d'oggi, le seguenti specie set è possibile: segnare il bit in una vasta gamma po 'di RAM per ogni numero che avete, quindi leggere loro fuori di nuovo attraverso la scansione della RAM. Un sacco di ottimizzazioni specifiche hardware possono essere applicati per le fasi di marchio e di scansione.