QSORT |
Tri rapide |
|---|---|
| Langage C | stdlib.h |
Syntaxe
| void qsort(void *tableau,size_t num,size_t size,int (*compar)(const void *px1,const void *px2); |
Paramètres
| Nom | Description |
|---|---|
| tableau | Ce paramètre permet d'indiquer le tableau à trier |
| num | Ce paramètre permet d'indiquer le nombre d'élément dans le tableau |
| size | Ce paramètre permet d'indiquer la taille d'un item du tableau |
| compar | Ce paramètre permet d'indiquer la fonction a utiliser pour la comparaison et doit retourner une valeur pour indiquer si les items sont inférieur, égale ou supérieur |
| px1 | Ce paramètre permet d'indiquer le premier item fonction a utiliser pour la comparaison |
| px2 | Ce paramètre permet d'indiquer le deuxième item fonction a utiliser pour la comparaison |
Description
Cette fonction permet d'effectuer un tri d'un tableau avec la méthode «QuickSort».
Algorithme
|
MODULE QSORT(base, num, size, compar) * Si le nombre d'éléments est inférieur ou égal à 1, ne rien faire SI num ≤ 1 ALORS RETOURNE FIN SI * Sélectionner un pivot (souvent l'élément du milieu ou aléatoire) pivot_index ← choose_pivot(num) * Partitionner le tableau autour du pivot left ← 0 right ← num - 1 BOUCLE FAIRE TANT QUE left ≤ right * Trouver un élément à gauche étant plus grand que le pivot BOUCLE FAIRE TANT QUE compar(base + left x size, base + pivot_index x size) < 0 left ← left + 1 FIN BOUCLE FAIRE TANT QUE * Trouver un élément à droite qui est plus petit que le pivot BOUCLE FAIRE TANT QUE compar(base + right x size, base + pivot_index x size) > 0 right ← right - 1 FIN BOUCLE FAIRE TANT QUE * Si les indices gauche et droit ne se sont pas croisés, échanger les éléments SI left ≤ right ALORS swap(base + left x size, base + right x size) left ← left + 1 right ← right - 1 FIN SI FIN BOUCLE FAIRE TANT QUE * Appliquer récursivement le tri à la partie gauche et droite du tableau SI right > 0 ALORS * Trier la partie gauche qsort(base, right + 1, size, compar) FIN SI SI left < num ALORS * Trier la partie droite qsort(base + left x size, num - left, size, compar) FIN SI |
Remarques
- Paramètres flexibles : Les quatre paramètres de qsort sont : un pointeur vers le tableau à trier base, le nombre d'éléments du tableau num, la taille de chaque élément size, et un comparateur compar déterminant l'ordre de tri. Le comparateur est une fonction comparant deux éléments à la fois, et devant retourner une valeur négative, zéro ou positive, en fonction de l'ordre souhaité.
- Utilisation d'une fonction de comparaison : Le comparateur passé à qsort est crucial pour son fonctionnement. Il doit être une fonction prenant deux paramètres, généralement des pointeurs vers les éléments à comparer, et retourne un entier :
- Un entier négatif si le premier élément est plus petit que le second.
- Zéro si les deux éléments sont égaux.
- Un entier positif si le premier élément est plus grand.
- Tri avec complexité O(n log n) : Le tri effectué par qsort repose sur l'algorithme de tri rapide (quicksort). Ce dernier est très performant, avec une complexité moyenne de O(n log n), ce qui en fait l'un des algorithmes de tri les plus rapides dans des cas généraux. Toutefois, dans le pire des cas, la complexité peut atteindre O(n2), mais cette situation est rare si l'algorithme est bien implémenté.
- Indépendance par rapport au type des éléments : L'un des principaux avantages de qsort est sa capacité à trier des tableaux de types différents grâce à son utilisation de pointeurs génériques. Cela permet à la fonction de trier n'importe quel type de données sans avoir besoin de redéfinir des fonctions de tri spécifiques pour chaque type.
- Limitation sur les types de données : Bien que qsort soit générique, il ne connaît pas le type des éléments qu'il trie, car il fonctionne uniquement avec des pointeurs void *. Par conséquent, il revient au programmeur de fournir une fonction de comparaison correcte connaissant les types des éléments du tableau. Cette flexibilité peut introduire des erreurs si le comparateur est mal conçu.
- Applications courantes : qsort est couramment utilisée dans des situations où un tableau de données doit être trié sans que le programmeur ait besoin de connaître à l'avance le type de données. Elle est particulièrement utile pour trier des structures complexes, des tableaux de chaînes de caractères, ou des structures personnalisées dans les applications.
- Problèmes de portabilité et de performance : Bien que qsort soit une fonction standard et portable, sa performance peut être affectée par la manière dont elle est implémentée par différents compilateurs et systèmes. De plus, le fait que qsort repose sur des pointeurs génériques peut introduire des problèmes de portabilité si les types de données sont mal manipulés.
Voir également
Langage de programmation - C - Référence de procédures et fonctions - bsearch
Langage de programmation - C++ - Référence de procédures et fonctions - qsort
Références
Langage C, Edition Micro-Application, Gehard Willms, 2001, ISBN: 2-7429-2008-0, page 733.
Borland C++ for Windows 4.0, Library Reference, Edition Borland, 1993, Part # BCP1240WW21772, page 204.
Dernière mise à jour : Mardi, le 28 juillet 2015