XXXVIII-A-1. Introduction▲

XXXVIII-A-2. Interface▲

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

XXXVIII-A-3. Comportement▲

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)

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

XXXVIII-B-1. Tri d'un tableau d'entiers▲

#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 ("=", a[i]);
   }
   printf ("\n");
}
 
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
   /* définir des pointeurs typés et initialisés
      avec les parametres */
   int const *pa = a;
   int const *pb = b;
 
   /* évaluer et retourner l'état de l'évaluation (tri croissant) */
   return *pa - *pb;
}
 
int main (void)
{
/* tableau a trier */
   int tab[] = { 4, 6, -3, 4, 7 };
 
/* affichage du tableau dans l'état */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau après le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
   return 0;
}

  4  6 -3  4  7
 -3  4  4  6  7
 
Press ENTER to continue.

XXXVIII-B-2. Tri d'un tableau de chaînes▲

#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)
{
   /* définir des pointeurs typés et initialisés
      avec les paramètres */
   char const *const *pa = a;
   char const *const *pb = b;
 
   /* évaluer et retourner l'état de l'évaluation (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'état */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau après le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
   return 0;
}

world
hello
wild
 
hello
wild
world
 
 
Press ENTER to continue.

XXXVIII-B-3. Tri d'un tableau de structures▲

#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 intermédiaire pour alléger l'écriture */
      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)
{
   /* définir des pointeurs typés et initialisés
      avec les paramètres */
   struct fiche const *pa = a;
   struct fiche const *pb = b;
 
   /* évaluer et retourner l'état de l'évaluation (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 à 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'état */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare_prenom);
 
/* affichage du tableau après le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare_age);
 
/* affichage du tableau après le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare_age_dec);
 
/* affichage du tableau après 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.

XXXVIII-B-4. Tri de nombres réels▲

#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;
}

Par défaut, la portée d'une fonction est globale.

int function (int a, char *b)
{
}

Elle est visible d'un autre module une simple déclaration :

int function ();

ou mieux, un prototype :

int function (int a, char *b);

Il est possible cependant de réduire la portée de la fonction à l'unité de compilation dans laquelle elle a été définie, en ajoutant le qualificateur static.

static int function (int a, char *b)
{
}

Cette pratique, lorsqu'elle est possible, apporte différents avantages :

• une économie d'identificateurs. La portée de celui-ci étant limitée à une unité de compilation, il est possible de le réutiliser pour une autre fonction qualifiée 'static' dans une autre unité de compilation ;
• une meilleure optimisation. Certains compilateurs sont capables d'"inliner" une telle fonction dans certaines conditions, ce qui diminue le temps d'exécution au prix d'une augmentation de la taille (le code de la fonction est recopié autant de fois que nécessaire) ;
• une meilleure organisation du code. Etant donné que ces fonctions sont forcément appelées par une fonction de l'unité de compilation dans laquelle elles ont été définies, le code se trouve naturellement organisé en blocs fonctionnels cohérents. De plus, comme à priori, ces fonctions n'ont pas besoin de prototypes séparés, cela favorise une organisation du fichier source selon le principe 'Définir avant d'utiliser' (Top-down)

On évitera cependant de multiplier les codes identiques, et les principes de factorisation du code restent en vigueur.

+--------------------+    +--------------------+
| Bloc fonctionnel A |    | Bloc Fonctionnel B |
+--------------------+    +--------------------+
               |               |
               v               v
             +--------------------+
             |       Outils       |
             +--------------------+

La portée d'un objet est régie selon plusieurs critères.

XL-B-1. Définition hors d'un bloc▲

XL-B-2. Définition dans un bloc▲

XL-B-3. Masquage (Shadowing)▲

/* objet de portée globale */
int x;
 
int f (void)
{
   /* la globale x est masquée par une locale du même nom */
   int x = 0;
 
   /* la globale x n'est pas modifiée. */
   x++;
}
 
int main (void)
{
   /* la globale x est modifiée */
   x = 2;
 
   f();
 
   /* la globale x vaut toujours 2 */
 
   return 0;
}

#include <stdio.h>
 
static void afficher (int const t[], size_t n)
{
   size_t i;
   for (i = 0; i <= n; i++)
   {
      printf ("M", t[i]);
   }
   printf ("\n");
}
 
 
int main (void)
{
   int tab[] = {1, 2, 3, 4};
 
   afficher (tab, sizeof tab / sizeof *tab);
   return 0;
}

Ce code parait correct, mais à l'exécution, on constate :

1   2   3   4   2
 
Press ENTER to continue.

Pour vérifier le comportement, je pose un piège qui vérifie la validité de l'index :

• il doit être >=0 (toujours vrai, vu le type size_t) ;
• il doit être < n.

Je vais donc ajouter un piège :

assert (i < n);

Avant l'accès en lecture au tableau.

Pour être valide, la conception du piège doit se faire sans lire le code à tester, mais en se basant uniquement sur l'interface et le comportement présumé.

#include <stdio.h>
#include <assert.h>
 
static void afficher (int const t[], size_t n)
{
   size_t i;
   for (i = 0; i <= n; i++)
   {
      /* ajout du piège */
      assert (i < n);
      printf ("M", t[i]);
   }
   printf ("\n");
}
 
int main (void)
{
   int tab[] = {1, 2, 3, 4};
 
   afficher (tab, sizeof tab / sizeof *tab);
   return 0;
}

Ce qui provoque bien sûr :

1   2   3   4Assertion failed: i < n, file main.c, line 10
 
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
 
Press ENTER to continue.

Ce qui signifie que i a dépassé la valeur maximale qu'autorise le langage C. La cause est évidemment le <= au lieu de < dans l'expression du for(), ce qui entraîne une action corrective immédiate :

#include <stdio.h>
#include <assert.h>
 
static void afficher (int const t[], size_t n)
{
   size_t i;
   /* correction */
   for (i = 0; i < n; i++)
   {
      /* ajout du piège */
      assert (i < n);
      printf ("M", t[i]);
   }
   printf ("\n");
}
 
int main (void)
{
   int tab[] = {1, 2, 3, 4};
 
   afficher (tab, sizeof tab / sizeof *tab);
   return 0;
}

L'exécution et, à présent, conforme aux attentes :

1   2   3   4
 
Press ENTER to continue.

Qui n'a jamais été confronté à ce problème :

Comment faire le lien entre des constantes symboliques et leur représentation textuelle ?

Le but des item-lists est de résoudre de façon la plus automatique possible ce genre de problème.

Le principe est de séparer les informations de bases constantes (par exemple, la correspondance entre caractère et chaîne morse) dans un fichier indépendant (ni.c, ni.h, on y reviendra), mais que l'on peut inclure (#include) de façon à réaliser une génération automatique de code en fonction de la demande.

Je prends un exemple plus parlant.

Je veux créer une série de constantes qui représentent des fruits

enum fruits
{ BANANE, ORANGE, POMME, FRAISE, KIWI };

Ca peut servir à définir une masse de fruit :

struct dosage_fruit
{
   enum fruits fruit;
   int masse;
};

puis des recettes de fruits mixés :

struct dosage_fruit mix_energie[] =
{
   {BANANE, 100},
   {ORANGE, 150},
   {FRAISE, 80},
};
 
struct dosage_fruit mix_forme[] =
{
   {BANANE, 50},
   {ORANGE, 50},
   {POMME, 100},
   {KIWI, 50},
   {FRAISE, 50},
};
 
// etc.

Si on veut afficher la recette, il faut un moyen simple pour convertir la constante fruit en une chaîne imprimable.

On va donc utiliser un tableau de chaînes construit sur le même modèle que le enum (même ordre, c'est primordial, car l'enum sert d'indice au tableau):

static char const *chaines_fruits[] =
{
   "banane",
   "orange",
   "pomme",
   "fraise",
   "kiwi",
};

ce qui permet maintenant d'afficher la composition :

void afficher_composition (char const *nom, struct dosage_fruit const *a,
                           size_t n)
{
   size_t i;
   printf ("%s\n", nom);
   for (i = 0; i < n; i++)
   {
      struct dosage_fruit const *p = a + i;
      printf ("%d g de %s\n", p->masse, chaines_fruits[p->fruit]);
   }
   printf ("\n");
}

que l'on appelle comme ceci :

#define N(a) (sizeof(a) / sizeof *(a))
 
{
   afficher_composition ("Mix energie", mix_energie, N(mix_energie));
   afficher_composition ("Mix forme", mix_forme, N(mix_forme));
 
   etc.

Ce qui donne

Mix energie
100 g de banane
150 g de orange
80 g de fraise
 
Mix forme
50 g de banane
50 g de orange
100 g de pomme
50 g de kiwi
50 g de fraise
 
 
Press ENTER to continue.

(je laisse au programmeur malin le soin d'écrire «d'orange» au lieu de «de orange»…)

Maintenant, patatras, nouvelle recette à la carte :

struct dosage_fruit mix_tropical[] =
{
   {BANANE, 50},
   {ORANGE, 80},
   {MANGUE, 100},
   {ANANAS, 50},
};

Quelles sont les conséquences sur le programme :

Deux modifications :

• l'enum :
   

  Sélectionnez

  enum fruits
  { BANANE, ORANGE, POMME, FRAISE, KIWI, MANGUE, ANANAS };

• la liste des chaînes 'associées' (manuellement, pour le moment) :

static char const *chaines_fruits[] =
{
   "banane",
   "orange",
   "pomme",
   "fraise",
   "kiwi",
   "mangue",
   "ananas",
};

Si j'inverse ou que j'en oubli une, c'est la catastrophe. Idem, et c'est beaucoup plus sournois, si j'oublie une ','.

Donc, après quelques sueurs froides, ça marche, et on obtient bien :

Mix energie
100 g de banane
150 g de orange
80 g de fraise
 
Mix forme
50 g de banane
50 g de orange
100 g de pomme
50 g de kiwi
50 g de fraise
 
Mix tropical
50 g de banane
80 g de orange
100 g de mangue
50 g de ananas
 
 
Press ENTER to continue.

Mais c'est déjà beaucoup de stress dans un petit programme comme ça. Dans l'industrie, la moyenne, c'est 1 000 000 de lignes… Pas question de se stresser comme ça si, pour ajouter une valeur dans la liste, il faut modifier dans 10 fichiers différents… (Lesquels ? On n'est pas des robots…)

Par contre, on peut utiliser des techniques de programmations qui font que la maintenance est centralisée en un seul fichier. On le modifie, on recompile tout le projet, et les modifications sont automatiquement reportées dans tout le code.

Pour ça, on va faire travailler la machine à partir d'un fichier unique, pour qu'elle produise ce qu'on veut. C'est toute la puissance qu'offre le préprocesseur bien maîtrisé.

Je vais montrer les différentes étapes pour expliquer le principe, mais dans la pratique, on ne fait que la dernière évidemment.

Dans notre exemple, Les deux éléments à "synchroniser" sont :

enum fruits
{ BANANE, ORANGE, POMME, FRAISE, KIWI, MANGUE, ANANAS };

et la liste des chaînes 'associées' (manuellement, pour le moment)

static char const *chaines_fruits[] =
{
   "banane",
   "orange",
   "pomme",
   "fraise",
   "kiwi",
   "mangue",
   "ananas",
};

Si on observe bien ces deux éléments, on constate qu'ils se ressemblent. Pour être plus parlant, on va les réorganiser en colonnes :

enum fruits
{
   BANANE,
   ORANGE,
   POMME,
   FRAISE,
   KIWI,
   MANGUE,
   ANANAS
};

et la liste des chaînes 'associées' (manuellement, pour le moment)

static char const *chaines_fruits[] =
{
   "banane",
   "orange",
   "pomme",
   "fraise",
   "kiwi",
   "mangue",
   "ananas",
};

On voit que le schéma est similaire :

• une entête ;
• une liste (chaque élément est terminé par une ,) ;
• une fin particulière.

On voit que la liste des enum présente une petite irrégularité : le dernier élément n'est pas terminé par une ','. C'est normal (et obligatoire) en C90 (en C99, la virgule est acceptée).

Petite astuce : on ajoute un élément à la liste, qui sert à terminer la liste sans virgule. Il ne fait pas partie de la liste. C'est soit un 'dummy' (inutile), soit, comme ici où les valeurs sont automatiques, une constante qui exprime le nombre d'éléments de la liste, ce qui, à priori, n'est pas complètement inutile…

Modification :

enum fruits
{
   BANANE,
   ORANGE,
   POMME,
   FRAISE,
   KIWI,
   MANGUE,
   ANANAS,
   NB_FRUITS
};

Afin de faciliter la maintenance, il faudrait disposer d'une liste 'double' comme ceci :

BANANE "banane"
ORANGE "orange"
POMME  "pomme"
FRAISE "fraise"
KIWI   "kiwi"
MANGUE "mangue"
ANANAS "ananas"

Comment faire comprendre ça à un programme C ?

C'est la qu'intervient la puissance du préprocesseur.

Il suffit d'écrire une liste de macros avec deux paramètres. Chaque macro représentant un groupe cohérent d'informations ou 'item' :

ITEM (BANANE, "banane")
ITEM (ORANGE, "orange")
ITEM (POMME , "pomme" )
ITEM (FRAISE, "fraise")
ITEM (KIWI  , "kiwi"  )
ITEM (MANGUE, "mangue")
ITEM (ANANAS, "ananas")

Il suffit ensuite d'écrire la définition de ITEM qui correspond à l'usage qu'on en fait :

enum fruits
{
#define ITEM(id, chaine)\
   id,
 
ITEM (BANANE, "banane")
ITEM (ORANGE, "orange")
ITEM (POMME , "pomme" )
ITEM (FRAISE, "fraise")
ITEM (KIWI  , "kiwi"  )
ITEM (MANGUE, "mangue")
ITEM (ANANAS, "ananas")
 
#undef ITEM
 
   NB_FRUITS
};

Ce qui va produire automatiquement la bonne liste.

On fait pareil avec l'autre liste :

static char const *chaines_fruits[] =
{
#define ITEM(id, chaine)\
   chaine,
 
ITEM (BANANE, "banane")
ITEM (ORANGE, "orange")
ITEM (POMME , "pomme" )
ITEM (FRAISE, "fraise")
ITEM (KIWI  , "kiwi"  )
ITEM (MANGUE, "mangue")
ITEM (ANANAS, "ananas")
 
#undef ITEM
};

Le #undef permet le 'recyclage' du nom de la macro qui est invariablement ITEM.

L'étape ultime consiste à inclure la liste à partir d'un fichier extérieur auquel je donne l'extension .itm (par exemple : fruits.itm semble approprié).

Je conseille de placer un commentaire dans ce fichier qui rappelle son nom et le début de la définition de la macro avec la signification des champs.

/* fruits.itm
 
#define ITEM(id, chaine)\
 
*/
ITEM (BANANE, "banane")
ITEM (ORANGE, "orange")
ITEM (POMME , "pomme" )
ITEM (FRAISE, "fraise")
ITEM (KIWI  , "kiwi"  )
ITEM (MANGUE, "mangue")
ITEM (ANANAS, "ananas")

La maintenance de ce fichier est extrêmement simple. Elle est «visuelle».

Les deux définitions deviennent alors :

enum fruits
{
#define ITEM(id, chaine)\
   id,
#include "fruits.itm"
#undef ITEM
 
   NB_FRUITS
};

et :

static char const *chaines_fruits[] =
{
#define ITEM(id, chaine)\
   chaine,
#include "fruits.itm"
#undef ITEM
};

Ce qui allège considérablement le code source et rend la maintenance automatique. (Le C, c'est Bien)

Il peut y avoir des centaines de lignes dans un .itm. Idem pour le nombre de champs. Ici, il y en a deux champs, mais on aurait pu en avoir qu'un seul. En effet, une macro sait transformer un paramètre symbolique (ORANGE) en une chaîne ("ORANGE") avec #. Mais elle ne sait pas modifier la casse des caractères, d'où mon choix de mettre deux champs.

Exemples de fichiers itm que j'utilise

(Simple) : gestion des erreurs

(Complexe) : tables de caractères

Je laisse au lecteur le soin d'écrire l'ensemble de l'exemple et de faire les tests nécessaires. Tous les éléments sont là.