QSORT

Syntaxe

Paramètres

Description

Cette fonction permet d'effectuer un tri d'un tableau avec la méthode «QuickSort».

Remarques

• La fonction qsort() trie le tableau pointé par tableau à l'aide d'un algorithme Quicksort. À la fin, le tableau sera trié. Le nombre d'éléments dans le tableau est spécifié par n, et la taille (en octets) de chaque élément est décrite par taille.
• La fonction pointée par comp est utilisée pour comparer un élément du tableau avec la clef. Le format de la fonction de comparaison doit être la suivante :

  int func_name(const void *arg1, const void *arg2);

  Elle doit renvoyer les valeurs décrites dans le tableau suivant :

  Valeur	Description
  < 0 (Moins que zéro)	Ces valeurs permettent d'indiquer que arg1 est inférieur à arg2.
  0 (Zéro)	Cette valeur permet d'indiquer que arg1 est égal à arg2.
  > 0 (Supérieur à zéro)	Ces valeurs permettent d'indiquer que arg1 est supérieur à arg2.

  Le tableau est trié par ordre croissant, l'adresse la plus basse contenant l'élément le plus bas.

• Définition et utilité : La fonction qsort est définie dans la bibliothèque <cstdlib> (ou <stdlib.h>) et permet de trier un tableau de manière générale, en utilisant l'algorithme de tri rapide (Quick Sort). Elle est très utile pour trier des tableaux de n'importe quel type de données, qu'il s'agisse de types primitifs ou de structures complexes, en fonction d'une fonction de comparaison personnalisée fournie par l'utilisateur.
• Utilisation avec des types primitifs : qsort peut être utilisée pour trier des tableaux d'éléments de types primitifs comme des int, float, char,... Cependant, il faut fournir une fonction de comparaison spécifique pour chaque type de données. Par exemple, pour trier un tableau d'entiers, la fonction de comparaison pourrait ressembler à ceci :
1. int compare_int(const void* a, const void* b) {
2.     return (*(int*)a - *(int*)b);
3. }

Cette fonction est ensuite passée à qsort pour comparer les éléments.

• Utilisation avec des structures complexes : Vous pouvez également utiliser qsort pour trier des tableaux de structures complexes. Cependant, la fonction de comparaison devra être adaptée pour prendre en compte les membres de la structure. Par exemple, pour trier un tableau d'objets de type Personne en fonction de leur âge, la fonction de comparaison pourrait être :
1. int compare_person(const void* a, const void* b) {
2.     return ((*(Personne*)a).age - (*(Personne*)b).age);
3. }


• Performance : qsort utilise l'algorithme de tri rapide (Quick Sort), ayant une complexité moyenne de O(n log n). Cependant, dans le pire des cas (si le tableau est déjà trié ou presque trié), la complexité peut atteindre O(n^2). Il est donc important de garder à l'esprit que la performance peut se détériorer dans certaines situations, et d'autres algorithmes de tri comme std::sort peuvent être plus efficaces dans des cas particuliers.
• Limitations de l'interface : Bien que qsort soit très générique, elle présente certaines limitations. Notamment, elle ne permet pas de trier des containers C++ modernes comme std::vector ou std::list directement, car elle nécessite que vous fournissiez un tableau brut. Par conséquent, dans le contexte C++, il est souvent préférable d'utiliser std::sort ou d'autres algorithmes de tri de la bibliothèque standard, étant mieux intégrés avec les conteneurs modernes et sont souvent plus performants.
• Sécurité et portabilité : L'utilisation de qsort peut entraîner des problèmes de sécurité, notamment si les fonctions de comparaison sont mal écrites et manipulent incorrectement les pointeurs, ce qui peut mener à des comportements indéfinis. Par ailleurs, comme qsort fait appel à des pointeurs void, l'accès aux éléments peut être moins sûr que dans des implémentations de tri basées sur des types spécifiques. De plus, bien que qsort soit largement supportée, elle est parfois perçue comme moins moderne par rapport aux fonctions de la bibliothèque standard C++ comme std::sort.

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.