Y at-il une bonne bibliothèque pour trier un grand tableau de nombres en C?

Question

Si j'ai un grand tableau d'entiers ou flotteurs, ce qui est un bon algorithme / mise en oeuvre pour le tri (en C)?

Il est un peu en retard dans le jeu pour une édition ... mais je suis à la recherche exactitude et Vitesse .

Answer 1

Pour les tableaux de tri des nombres, considérons un algorithme de tri radix. Lorsqu'il est correctement conçu, ces sortes devraient fournir de meilleures performances que GLIBC qsort ().

La bibliothèque usort contient des implémentations de type spécifique pour tous les principaux types numériques C.

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

L'avantage de la vitesse de tri radix sur GLIBC qsort est d'environ 2,5x pour les nombres à virgule flottante double précision à N = 1000000 sur mon ordinateur portable intel 64 bits. Cependant, comme N pousse l'avantage devrait être d'autant plus grande tri radix est un algorithme linéaire nécessitant un nombre constant de passages à travers les données.

Pour tout petit N, le même code envoie une sorte de introsort ou l'insertion.

Answer 2

qsort () de la bibliothèque standard est un good'un.

Les fonctions de comparaison serait négligeable pour ces cas:

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 version de ces en soustrayant b d'un compte sur le comportement de débordement signé, il est donc pas une bonne idée)

Answer 3

Il est jamais une mauvaise idée d'utiliser qsort ... à moins que vous savez quelque chose sur les chiffres.

Vous avez marqués avec tri radix. Combien de mémoire êtes-vous prêt à investir? Les chiffres à l'intérieur d'une plage spécifique? Est-ce qu'ils ont des propriétés qui rend le tri radix faisable?

Sauf si vous voulez utiliser beaucoup de mémoire, qsort est une excellente option.

Answer 4

Étant donné une énorme quantité de RAM que nous obtenons de nos jours, le genre jeu suivant est possible: marquer le bit dans un tableau énorme de bit de RAM pour chaque numéro que vous avez, puis les consulter en arrière en balayant la RAM. Beaucoup d'optimisations spécifiques au matériel peuvent être appliqués pour les phases de marquage et de scannage.