Comprendre l'algorithme QuickSort : diviser pour mieux régner

Dans le monde de l'informatique, QuickSort s'impose comme l'un des algorithmes de tri les plus efficaces et les plus utilisés. Sa rapidité remarquable dans le tri de grands ensembles de données est due à sa stratégie « Diviser pour régner ». Découvrons comment fonctionne QuickSort !

Qu'est-ce que QuickSort ?

QuickSort est un algorithme de tri qui utilise la technique « Divide and Conquer ». Il sélectionne un élément, appelé pivot, et divise la liste en deux sous-tableaux : un contenant des éléments plus petits que le pivot et un autre avec des éléments plus grands. Le processus se répète de manière récursive sur ces sous-tableaux jusqu'à ce que la liste soit complètement triée.

Le choix du pivot peut varier. Une approche simple consiste à sélectionner le premier élément de la liste. Cependant, d'autres stratégies peuvent être plus efficaces selon le scénario.

Étapes de tri rapide

1. Critère d'arrêt de récursion

Lorsque la liste contient 0 ou 1 élément, elle est déjà triée et l'algorithme se termine.

<code class="language-java">// Verifica se a lista tem 0 ou 1 elemento (já ordenada)
if (integerList.isEmpty() || integerList.size() == 1) {
    return integerList;
}</code>

2. Partitionnement de liste :

L'étape suivante consiste à sélectionner un pivot et à diviser la liste en deux sous-tableaux : l'un avec des éléments plus petits et l'autre avec des éléments plus grands que le pivot. Voir un exemple de la façon dont cela peut être fait :

<code class="language-java">int pivo = integerList.get(0); // Escolhendo o primeiro elemento como pivô
List<Integer> menores = new ArrayList<>();
List<Integer> maiores = new ArrayList<>();
for (int i = 1; i < integerList.size(); i++) {
   if (integerList.get(i) < pivo) {
      menores.add(integerList.get(i));
   } else {
      maiores.add(integerList.get(i));
   }
}</code>

Remarque : Notez que la comparaison commence à i=1, empêchant le pivot d'être inclus dans le sous-tableau des mineurs.

3. Récursivité :

La récursivité entre en jeu ! L'algorithme s'appelle les sous-tableaux les plus petits et les plus grands, répétant le processus jusqu'à ce que le tri soit complet. La combinaison des résultats est démontrée ci-dessous :

<code class="language-java">List<Integer> sorted = new ArrayList<>(quickSort(menores));
sorted.add(pivo);
sorted.addAll(quickSort(maiores));
return sorted;</code>

Complexité de l'algorithme

QuickSort a une complexité temporelle asymptotique de O(n log n), démontrant une grande efficacité, en particulier par rapport aux algorithmes tels que Bubble Sort, qui a une complexité O(n²).

Remarque : Cette explication est une adaptation basée sur le chapitre 4 du livre "Comprendre les algorithmes" d'Aditya Bhargava. Il est à noter qu'il peut y avoir des nuances non abordées ici, et il est recommandé de consulter des sources supplémentaires pour une étude plus approfondie.

Conclusion

QuickSort est un algorithme robuste qui utilise la récursion pour trier efficacement les listes. Son principal attribut est la vitesse d’exécution, notamment sur les listes longues, par rapport aux autres algorithmes de tri. Pour une compréhension plus complète, la lecture du livre « Comprendre les algorithmes » est suggérée.

Avez-vous déjà utilisé QuickSort dans un projet ? Partagez votre expérience dans les commentaires !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!