qsort() : tri d'un tableau sur lui-même (méthode:tri rapide)
Prototype:
void qsort( void * tab, size_t nt, size_t taille, int (*fcmp)(const void *px1, const void *px2));
dans: <stdlib.h>
Description:
Le sous-programme qsort() trie les nt éléments du tableau tab, par la méthode quick-sort.
La comparaison entre deux éléments est définie par le quatrième paramètre, qui est une fonction recevant les adresses p1 et p2 des éléments à comparer et renvoie:
- un entier négatif si *p1 est inférieur à *p2 + 0 si *p1 est égal à *p2
- un entier positif si *p1 est supérieur à *p2.
Le paramètre taille doit indiquer la taille en octets d'un élément de tab; c'est aussi la taille des zones à échanger par l'algorithme de tri.
Voir aussi:
Portabilité:
Exemple:
<![CDATA[
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
qsort() est d'abord utilisé pour trier un tableau de
mots en utilisant l'ordre lexicographique lié au
code ascii.
Dans un deuxième exemple, un tableau d'entiers est trié
par ordre décroissant.
Un tableau a deux dimensions de mots est trié dans le
dernier exemple.
*/
/* Type pointeur sur caractère */
typedef char * Pchar;
/* TFcmp: Type pointeur sur fonction de comparaison */
typedef int (* TFcmp) (const void *p1, const void *p2) ;
/* Deux fonctions de comparaisons */
int cmpMot( const void * m1, const void * m2);
int cmpEntier( const void * pm1, const void * pm2);
int main (void) {
/* Premier exemple: tableau de mots */
static Pchar liste[]={"alexandre","Aline","abel","andré","Andrée"};
/* Deuxième exemple: tableau d'entiers */
static int ti[]={ 17, 25, 21, 25, 19, 23};
/* Troisième exemple: tableaux à deux dimensions (6 colonnes) */
static char tc2[][6]={"alexa","Aline","abel ","andré","André"};
/* Tailles respectives de chaque tableau */
int i, nl = sizeof(liste)/sizeof(liste[0]),
nti = sizeof(ti)/sizeof(ti[0]),
ntc2 = sizeof(tc2)/sizeof(tc2[0]) ;
/* Premier tri avec la fonction de comparaison cmpMot */
printf("\nAvant tri:");
for (i=0; i<nl; i++) printf(" %s", liste[i]);
qsort( liste, nl, sizeof(liste[0]), cmpMot);
printf("\nAprès tri:");
for (i=0; i<nl; i++) printf(" %s", liste[i]);
/* Deuxième tri avec la fonction de comparaison cmpEntier qui permet
de trier par ordre décroissant */
printf("\n\nAvant tri:");
for (i=0; i<nti; i++) printf(" %d", ti[i]);
qsort( ti, nti, sizeof(int), cmpEntier);
printf("\nAprès tri:");
for (i=0; i<nti; i++) printf(" %d", ti[i]);
/* Troisième tri avec la fonction de comparaison standard strcmp */
printf("\n\nAvant tri:");
for (i=0; i<ntc2; i++) printf(" %s", tc2[i]);
qsort( tc2, ntc2, sizeof(tc2[0]), (TFcmp) strcmp);
printf("\nAprès tri:");
for (i=0; i<ntc2; i++) printf(" %s", tc2[i]);
printf("\n");
return 0;
}
int cmpMot( const void * mot1, const void * mot2) {
return strcmp(*(Pchar*)mot1, *(Pchar*)mot2) ;
}
int cmpEntier( const void * p1, const void * p2) {
/* comparaison pour ordre décroissant */
typedef const int * PEntierConstant;
PEntierConstant pi1 = (PEntierConstant)p1,
pi2 = (PEntierConstant)p2;
return *pi2 - *pi1 ;
}
]]>