Du bon usage de la fonction qsort()

Dernière mise à jour : 25/04/2009 21:28:20 Merci à hiveNzin0 pour la relecture

Un forum web "Bien programmer en C" permet de poser des questions sur les articles, le C en général, la programmation etc.

Home

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

Interface de la fonction de comparaison

Cette fonction dispose de 2 paramètres :

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

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.


Valid XHTML 1.0! Valid CSS! Get Firefox!  Use OpenOffice.org Club d'entraide des développeurs francophones Code::Blocks
© Emmanuel Delahaye 2007-2009 | emmanuel dot delahaye at gmail dot com | Up | Home | Forum | Livre d'or