Au chapitre 5, vous avez vu une méthode de tri simple appelée
tri des bulles. Il a été mentionné à cette époque qu'il y avait
des notes nettement meilleures. Ici, vous développerez une version de l'un des meilleurs : le tri rapide (Quicksort).
Classification rapide, inventée et nommée par C.A.R. Hoare, est le meilleur algorithme de classification à usage général actuellement disponible. Je n'ai pas pu le montrer au chapitre 5 car la meilleure implémentation du tri rapide est basée sur la récursivité. La version que nous développerons trie un tableau de caractères, mais la logique peut être adaptée pour trier tout type d'objet.
Le tri rapide est basé sur l'idée de partitions. La procédure générale consiste à sélectionner une valeur, appelée comparaison, puis à diviser le tableau en deux sections. Tous les éléments supérieurs ou égaux à la valeur de partition sont insérés d'un côté et les plus petits sont insérés de l'autre. Ce processus est répété pour chaque section restante jusqu'à ce que le tableau soit trié. Par exemple, étant donné le tableau fedacb et en utilisant la valeur d comme comparaison, la première passe de tri rapide réorganiserait le tableau comme indiqué ci-dessous :

Initial f e d a c b
Passage 1 b c a d e f

Ce processus est ensuite répété pour chaque section, c'est-à-dire bca et def. Comme vous pouvez le constater, le processus est essentiellement de nature récursive, et en fait, la mise en œuvre la plus propre du tri rapide est récursive.
Vous pouvez sélectionner la valeur de comparaison de deux manières. Vous pouvez le sélectionner au hasard ou en trouvant la moyenne d'un petit ensemble de valeurs extraites du tableau. Pour obtenir une classification optimale, vous devez sélectionner une valeur qui se situe exactement au milieu de la plage de valeurs. Cependant, cela n’est pas facile à réaliser pour la plupart des ensembles de données. Le pire des cas est lorsque la valeur sélectionnée se trouve à une extrémité. Malgré tout, le tri rapide fonctionnera correctement.
La version du tri rapide que nous allons développer sélectionne l'élément central du tableau comme comparaison.

Voir QSDemo.java.

Tri rapide :

• L'un des algorithmes de classification les plus efficaces et les plus utilisés.
• Inventé par C.A.R. Hoare.
• Basé sur le concept de partitions, où le tableau est divisé en sections triées de manière récursive.
• Plus efficace que le tri à bulles et d'autres méthodes simples.

Opération:

• Valeur de comparaison (pivot) :
• Une valeur est choisie comme référence (pivot) et le tableau est organisé autour de cette valeur.
• Les éléments plus petits que le pivot vont d'un côté et les plus grands de l'autre.
• Le processus est répété de manière récursive pour chaque section jusqu'à ce que le tableau soit complètement trié.

Tri rapide

QSDémo