Fonction de bibliothèque C pour effectuer le tri

Existe-t-il une fonction de bibliothèque disponible dans la bibliothèque standard C pour effectuer le tri?

qsort()est la fonction que vous recherchez. Vous l'appelez avec un pointeur vers votre tableau de données, le nombre d'éléments dans ce tableau, la taille de chaque élément et une fonction de comparaison.

Il fait sa magie et votre tableau est trié sur place. Un exemple suit:

#include <stdio.h>
#include <stdlib.h>
int comp (const void * elem1, const void * elem2) 
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}
int main(int argc, char* argv[]) 
{
    int x[] = {4,5,2,3,1,0,9,8,6,7};

    qsort (x, sizeof(x)/sizeof(*x), sizeof(*x), comp);

    for (int i = 0 ; i < 10 ; i++)
        printf ("%d ", x[i]);

    return 0;
}

La bibliothèque standard C / C ++ <stdlib.h>contient une qsortfonction.

Ce n'est pas la meilleure implémentation de tri rapide au monde mais elle est assez rapide et TRÈS FACILE à utiliser ... la syntaxe formelle de qsort est:

qsort(<arrayname>,<size>,sizeof(<elementsize>),compare_function);

La seule chose que vous devez implémenter est la fonction compare_function, qui prend deux arguments de type "const void", qui peuvent être convertis en une structure de données appropriée, puis renvoyer l'une de ces trois valeurs:

• négatif, si a doit être avant b
• 0, si a égal à b
• positif, si a doit être après b

1. Comparaison d'une liste d'entiers :

simplement coulé a et b des nombres entiers de cas x < y, x-yest négative, x == y, x-y = 0, x > y, x-yest positif x-yest un moyen de raccourci pour le faire :) inverse *x - *yà *y - *xde tri décroissant / ordre inverse

int compare_function(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}

2. Comparaison d'une liste de chaînes :

Pour comparer une chaîne, vous avez besoin d'une strcmpfonction dans <string.h>lib. strcmpretournera par défaut -ve, 0, ve de manière appropriée ... pour trier dans l'ordre inverse, inversez simplement le signe renvoyé par strcmp

#include <string.h>
int compare_function(const void *a,const void *b) {
return (strcmp((char *)a,(char *)b));
}

3. Comparaison des nombres à virgule flottante :

int compare_function(const void *a,const void *b) {
double *x = (double *) a;
double *y = (double *) b;
// return *x - *y; // this is WRONG...
if (*x < *y) return -1;
else if (*x > *y) return 1; return 0;
}

4. Comparaison des enregistrements en fonction d'une clé :

Parfois, vous devez trier des éléments plus complexes, tels que des enregistrements. Voici le moyen le plus simple de le faire à l'aide de la qsortbibliothèque.

typedef struct {
int key;
double value;
} the_record;

int compare_function(const void *a,const void *b) {
the_record *x = (the_record *) a;
the_record *y = (the_record *) b;
return x->key - y->key;
}

Bien sûr: qsort()est une implémentation d'une sorte (pas nécessairement de tri rapide comme son nom pourrait le suggérer).

Essayez man 3 qsort ou lisez-le sur http://linux.die.net/man/3/qsort

Bien que n'étant pas exactement dans la bibliothèque standard, https://github.com/swenson/sort ne contient que deux fichiers d'en-tête que vous pouvez inclure pour accéder à un large éventail de routages de tri incroyablement rapides, comme ceci:

#define SORT_NAME int64 #define SORT_TYPE int64_t #define SORT_CMP ( x , y ) (( x ) - ( y )) #include "sort.h" / * Vous avez maintenant accès à int64_quick_sort, int64_tim_sort, etc., par exemple * / 
int64_quick_sort ( arr , 128 ); / * Suppose que vous avez des int * arr ou int arr [128]; * /

   
 
  

Cela devrait être au moins deux fois plus rapide que la bibliothèque standard qsort, car elle n'utilise pas de pointeurs de fonction et propose de nombreuses autres options d'algorithme de tri.

Il est en C89, il devrait donc fonctionner dans pratiquement tous les compilateurs C.

essayez qsortdans stdlib.h.

Utiliser qsort()dans <stdlib.h>.

@paxdiablo La qsort()fonction est conforme à la norme ISO / CEI 9899: 1990 (`` ISO C90 '').

Plusieurs fonctions de tri C sont disponibles dans stdlib.h . Vous pouvez faire man 3 qsortsur une machine unix pour en obtenir une liste, mais ils incluent:

• tas de choses
• tri rapide
• tri par fusion