Fonction Qsort
La fonction Qsort permet de trier une liste d'indice, en faisant appel à une fonction de retour permettant de faire une comparaison élémentaire entre deux éléments.
La fonction de retour a deux paramètres l'indice d ’accès de gauche et l'indice d ’accès de droite ; ce sont des entiers compris entre 0 et Nombre-1 . Nombre est le nombre d'élément de l'ensemble à trier.
L'application la plus courante est le tri d'un tableau.
Soit par exemple une table quelconque contenant des valeurs à trier, on veut pouvoir la balayer dans l'ordre des valeurs croissantes.
Var MaTable Array[NbLigne]; MaListe List; ... Function MaComparaison(gauche, droite) // Ici pour un ordre croissant // Pour un ordre décroissant on inverse les valeurs +1 et -1 begin if MaTable[gauche] < MaTable[droite] then return -1; else if MaTable[gauche] == MaTable[droite] then return 0; else return +1; end
... // Preparation de la liste d'indice avant tri, ici on les prend tous // de 0 à NbLigne-1 MaListe.ordered(NbLigne); // Obtention de la liste triée Qsort( MaListe, MaComparaison);
// Balayage de la table en suivant les valeurs triées for i in Maliste do Message( MaTable[i]);
Après l'appel de la fonction Qsort (pour l'anglais Quick Sort), la liste MaListe a été complètement recréée en une liste d'entiers de longueur NbLigne et dont chaque ligne est l'indice d ’accès au tableau MaTable dans l'ordre attendu.
Il faut noter que Qsort n ’accède pas directement à ma table, il se contente d'appeler une fonction de retour, ici MaComparaison, qui elle interroge MaTable ; cette fonction QSort peut donc être utilisée pour trier tout ensemble de données quelque soit son type, il suffit que l'on puisse accéder à chaque élément par un indice.