QSORT

La fonction qsort permet de trier un tableau d'éléments quelconques en utilisant l'algorithme “Quick Sort” ou tri rapide.

Cette fonction fait partie de la librairie stdlib.h.

void qsort(const void *tableau,
           size_t NombreElements,
           size_t TailleElemetns,
           int (*cmp)(const void *, const void *)) /* la fonction qui compare les elements */

Le premier argument est un pointeur vers un tableau d'éléments. Les deux paramètres suivants sont le nombre d'éléments du tableau et la taille d'un élément du tableau. Avec ces trois paramètres, l'algorithme est capable de manipuler un tableau banalisé.

Le dernier élément a passer en paramètre, est un pointeur vers une fonction de comparaison de deux éléments. cette fonction de comparaison recoit deux pointeurs vers les deux éléments à comparer. Vous devez retourner un entier positif si le premier élément est avant le deuxième, un entier négatif si le premier élément est après le deuxième. En cas d'égalité, vous devez retourner 0.

Quelques exemples de fonction de comparaison :

Comparaison de deux réels

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

Notez bien l'utilisation des cast pour ne pas avoir de warning lors de la compilation.

Comparaison de deux étoiles

Dans cet exemple, on remarque que l'on peut utiliser qsort pour trier une liste d'objets. Il suffit de définir la fonction de comparaison. Une étoile est plus grande qu'une autre si son intensité (la somme des valeurs de pixels qui la compose) est plus grande que l'autre étoile.

int cmp_etoile(const void *x, const void  *y){
  struct etoile **A=(struct etoile **)x;
  struct etoile **B=(struct etoile **)y;
 
  uint32 a=  (*A)->intensite;
  uint32 b=  (*B)->intensite;
 
  if (a<b) return 1;
  if (a>b) return -1;
  return 0;
}