Bibliothèque standard du C : qsort()

Description de la fonction qsort()

Introduction

La fonction qsort() implémente un algorithme de tri non spécifié qui permet de trier tout ou partie de n'importe quel tableau de données, du moment qu'il existe un critère de tri dans les données. Elle s'appuie sur une fonction utilisateur qui se charge d'exprimer le critère de tri.

C'est l'implémentation qui décide quel algorithme est utilisé. En général, l'algorithme est choisi pour sa performance. Il n'est pas rare que ce soit un Quick Sort.

Interface

Le prototype de la fonction qsort() est

void qsort (void *tableau
            , size_t nb_elem
            , size_t taille_elem
            , int (*compare) (void const *a, void const *b));

Les paramètres sont

void *tableau : C'est l'adresse du premier élément du tableau à trier. La partie à trier doit être modifiable.
size_t nb_elem : C'est le nombre d'éléments du tableau à trier (à ne pas confondre avec sa taille) :
Par exemple, tout le tableau : sizeof tab / sizeof *tab.
size_t taille_elem : C'est la taille d'un élément du tableau : sizeof *tab.
int (*compare) (void const *a, void const *b) : c'est l'adresse de la fonction de comparaison (pointeur de fonction). Cette fonction est fournie par l'utilisateur.

Interface de la fonction de comparaison

Cette fonction dispose de 2 paramètres :

void const *a : C'est l'adresse d'un des éléments du tableau en cours d'évaluation par l'algorithme. Il est qualifié 'const', car la fonction de comparaison ne doit en aucun cas en modifier le contenu sous peine de comportement indéfini.
void const *b : C'est l'adresse d'un autre élément du tableau en cours d'évaluation par l'algorithme. Il est qualifié 'const', car la fonction de comparaison ne doit en aucun cas en modifier le contenu sous peine de comportement indéfini.

de plus, elle doit retourner un int qui prend la valeur suivante (tri croissant) :

0 si le critère de a est égal au critère de b
< 0 si le critère de a est inférieur au critère de b
> 0 si le critère de a est supérieur au critère de b

Comportement

La fonction qsort() effectue le tri du tableau selon le critère indiqué. La valeur rétournée par la fonction de comparaison permet à l'algorithme de prendre les décisions qui s'imposent.

Comportement de la fonction de comparaison

La fonction de comparaison reçoit l'adresse des 2 éléments en cours d'évaluation. Par l'intérmédiare de pointeurs locaux typés et initialisés avec ces paramètres, elle doit evaluer le critère de tri et retourner un int de la valeur résultant de l'évaluation. Pour un entier, une simple différence suffit. Pour une chaine, str[n]cmp() a été conçue pour ça. Pour un réel, c'est plus délicat, car la notion d'égalité est soumise à l'appréciation d'un EPSILON qui dépend de la précision recherchée.

Usage de la fonction qsort()

Afin de dédramatiser l'usage de qsort(), qui fait parfois un peu peur, je fournis ici quelques exemples d'utilisation.

Attention, je suppose que les bases du C sont connues (tableaux, pointeurs, fonctions, I/O)

Tri d'un tableau d'entiers

Soit un tableau de 5 entiers à trier : 4 , 6, -3, 4, 7,

#include <stdio.h>
#include <stdlib.h>

/* affichage du tableau */
static void aff (int *a, size_t n)
{
   size_t i;
   for (i = 0; i < n; i++)
   {
      printf ("%3d", a[i]);
   }
   printf ("\n");
}

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   int const *pa = a;
   int const *pb = b;

   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return *pa - *pb;
}

int main (void)
{
/* tableau a trier */
   int tab[] = { 4, 6, -3, 4, 7 };

/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);

   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);

/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);

   return 0;
}

Ce qui donne :

  4  6 -3  4  7
 -3  4  4  6  7

Press ENTER to continue.

Exercice : Ecrire le code qui fait le tri décroissant.

Tri d'un tableau de chaines

Il s'agit maintenant de trier un tableau de chaines constantes. Ici, il est particulièrement important de bien comprendre le sens de 'const'. Le tableau est modifiable, mais il est composé de pointeurs sur des chaines non modifiables. Ce que va faire qsort(), c'est de réorganiser le tableau de pointeurs de façon à ce lorsqu'on lira le tableau en séquence, les chaines pointées apparaissent comme 'triées'. Ce concept est assez subtil, car le tri est indirect. En effet, si on regardait la valeur des pointeurs dans le tableau, ils ne seraient probablement pas triés. De même, les chaines en mémoire non modifiable sont, par définition, réstées à leur place.

Dans la fonction de comparaison, comme d'habitude, on récupère les adresse des éléments en cours d'évaluation. Ici, les éléments sont de type char const *. Leur adresse est donc de type char const * *. Mais comme on a pas le droit de modifier les données pointées, on doit ajouter un 'const' pour être conforme aux paramètres : char const * const *

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* affichage du tableau */
static void aff (char const **a, size_t n)
{
   size_t i;
   for (i = 0; i < n; i++)
   {
      printf ("%s\n", a[i]);
   }
   printf ("\n");
}

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   char const *const *pa = a;
   char const *const *pb = b;

   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (*pa, *pb);
}

int main (void)
{
/* tableau a trier (tableau de pointeurs sur char const) */
   char const *tab[] = { "world", "hello", "wild" };

/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);

   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);

/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);

   return 0;
}

malgré tout, le tri a eu lieu :

world
hello
wild

hello
wild
world


Press ENTER to continue.

Tri d'un tableau de structures

Soit une structure comprenant {nom, prenom, age}. On crée un tableau de 5 éléments de ce type que l'on remplit "à la main", puis, on fait un tri par prenom, par age décroissant, puis par age croissant.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct fiche
{
   char nom[11];
   char prenom[11];
   int age;
};

/* affichage du tableau */
static void aff (struct fiche const *a, size_t n)
{
   size_t i;
   for (i = 0; i < n; i++)
   {
      /* pointeur intermediaire pour alleger l'ecriture */
      struct fiche const *p = a + i;
      printf ("%-10s %-10s %d ans\n", p->nom, p->prenom, p->age);
   }
   printf ("\n");
}

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare_prenom (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   struct fiche const *pa = a;
   struct fiche const *pb = b;

   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (pa->prenom, pb->prenom);
}

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare_age (void const *a, void const *b)
{
   struct fiche const *pa = a;
   struct fiche const *pb = b;

   return pa->age - pb->age;
}

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare_age_dec (void const *a, void const *b)
{
   struct fiche const *pa = a;
   struct fiche const *pb = b;

   return pb->age - pa->age;
}

int main (void)
{
/* tableau a trier (tableau de pointeurs sur char const) */
   struct fiche tab[] = {
      {"Simpson", "Homer", 36},
      {"Bouvier", "Marge", 34},
      {"Simpson", "Bart", 10},
      {"Simpson", "Lisa", 8},
      {"Simpson", "Maggie", 2},
   };

/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);

   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare_prenom);

/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);

   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare_age);

/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);

   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare_age_dec);

/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);

   return 0;
}

Simpson    Homer      36 ans
Bouvier    Marge      34 ans
Simpson    Bart       10 ans
Simpson    Lisa       8 ans
Simpson    Maggie     2 ans

Simpson    Bart       10 ans
Simpson    Homer      36 ans
Simpson    Lisa       8 ans
Simpson    Maggie     2 ans
Bouvier    Marge      34 ans

Simpson    Maggie     2 ans
Simpson    Lisa       8 ans
Simpson    Bart       10 ans
Bouvier    Marge      34 ans
Simpson    Homer      36 ans

Simpson    Homer      36 ans
Bouvier    Marge      34 ans
Simpson    Bart       10 ans
Simpson    Lisa       8 ans
Simpson    Maggie     2 ans


Press ENTER to continue.

Nombres réels

Pour trier les nombres réels (float, double), il y a quelques précautions à prendre, car la notion d'égalité n'existe pas. Il faut travailler par plages :

#include <stdio.h>
#include <time.h>

double random_range (double min, double max)
{
   return min + ((max - min) * (rand () / (double) RAND_MAX));
}

static int cmp (void const *a, void const *b)
{
   int ret = 0;
   double const *pa = a;
   double const *pb = b;
   double diff = *pa - *pb;
   if (diff > 0)
   {
      ret = 1;
   }
   else if (diff < 0)
   {
      ret = -1;
   }
   else
   {
      ret = 0;
   }

   return ret;
}

int main (void)
{
   double tab[100];
   int i;
   srand ((int) time (NULL));
   for (i = 0; i < sizeof tab / sizeof *tab; i++)
   {
      tab[i] = random_range (0, 1);
   }

   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, cmp);

   for (i = 0; i < sizeof tab / sizeof *tab; i++)
   {
      printf ("%8.4f", tab[i]);
   }

   return 0;
}

Ces exemples ne sont pas des suites de validation d'algorithmes de tri !
Ce ne sont que de simples exemples.