Vue d’ensemble des algorithmes de tri Quicksort

Vue d'ensemble du tri Quicksort

Découvrez l’un des algorithmes de tri les plus efficaces

Introduction

Le quicksort est probablement l’algorithme de tri le plus populaire. Dans de nombreuses expériences, il a été démontré qu’en moyenne, il est plus performant que d’autres méthodes de tri telles que le tri fusion ou le tri par tas.

Le quicksort est basé sur l’idée de diviser récursivement un tableau en deux parties : la première qui contient tous les éléments inférieurs à un élément pivot et la deuxième qui est composée des éléments supérieurs. Cette procédure s’appelle partition. La fonction de partition est appelée récursivement sur les deux parties divisées du tableau jusqu’à ce qu’il ne reste qu’un seul élément à partitionner.

Partition

Initialement, il est nécessaire de choisir un élément pivot. Celui-ci peut être n’importe quel élément du tableau. Dans notre exemple, nous choisirons le dernier élément du tableau. Ensuite, nous parcourons une boucle où à chaque itération, nous comparons l’élément courant au pivot. Si l’élément est inférieur ou égal au pivot, il est conservé dans la partie gauche du tableau. Sinon, l’élément est déplacé vers la partie droite.

• Le Guide Ultime pour Entraîner BERT à partir de Zéro Préparer le Jeu de Données
• Comment évaluer les représentations
• Représentation du chemin en Python

Tout d’abord, nous initialisons deux pointeurs : i et j. L’indice j pointe vers le premier élément tandis que i pointe vers sa valeur précédente j – 1. Avec les variables introduites i et j, les invariants suivants sont satisfaits tout au long de la boucle :

• Les éléments d’indices [gauche, i] sont inférieurs ou égaux au pivot.
• Les éléments d’indices [i + 1, j) sont supérieurs au pivot.

À la fin de la boucle, j sera égal à droite et l’indice i divisera le tableau en deux parties. Grâce aux invariants vrais, notre tableau sera correctement partitionné.

À chaque itération, j est incrémenté de 1, il pointe donc toujours vers l’élément actuel. Ensuite, l’élément courant array[j] est comparé au pivot. Si l’élément est inférieur ou égal au pivot, il est échangé avec l’élément à la position i + 1. Selon l’invariant mentionné ci-dessus, nous savons toujours que array[i + 1] > pivot. Par conséquent, l’élément qui est inférieur ou égal au pivot est échangé vers la gauche avec un élément qui est supérieur au pivot. En effectuant un tel échange, notre invariant est violé. Pour rendre l’invariant correct après cela, i est incrémenté de 1.

Si array[j] > pivot, alors l’invariant est toujours correct et nous passons simplement à l’itération suivante (i ne change pas de valeur).

Il est facile de remarquer qu’après toutes les itérations, le tableau sera correctement partitionné. La logique décrite est démontrée dans l’extrait de code ci-dessous. Remarquez que l’indice de l’élément pivot est renvoyé.

Fonction de partition

Tri

L’algorithme de tri se déroule de manière récursive. Tout d’abord, le tableau est partitionné en deux parties, selon la section précédente. Pour chacun d’eux, la procédure de partition est invoquée de manière récursive jusqu’au moment où il ne reste qu’un seul élément à partitionner.

La fonction pour cet algorithme est présentée ci-dessous.

Fonction quicksort

Complexité

Étant donné que la preuve asymptotique précise pour quicksort comprend trop de détails et est relativement complexe, je ne souhaite pas entrer dans tous les aspects mais fournir une preuve informelle.

Lors de chaque appel de partition, nous parcourons linéairement tous les éléments d’un tableau, ce qui entraîne une complexité O(K) où K est la taille du tableau. Supposons qu’après chaque procédure de partition, l’élément pivot sépare le tableau en deux moitiés égales, nous appelons récursivement la fonction quicksort pour chacune d’entre elles jusqu’à ce qu’il ne reste qu’un seul élément à trier. Cela donne la structure d’appel de fonction suivante qui ressemble à celle du tri fusion.

La seule différence est qu’au lieu de la fonction merge, nous appelons la fonction partition mais les deux ont la même complexité temporelle O(K). Étant donné que la structure hiérarchique est également la même, nous concluons que la complexité temporelle pour le tri rapide est O(N * logN). La preuve asymptotique pour le tri fusion peut être trouvée ici.

Algorithmes de tri, Partie 1 : Tri fusion

Quand il s’agit de tri, le tri fusion est l’un des algorithmes les plus populaires. Il est basé sur le célèbre…

VoAGI.com

Dans la preuve ci-dessus, nous avons supposé que le tableau est toujours partitionné en deux moitiés égales, ce qui n’est évidemment pas toujours vrai. Supposons que la procédure de partition sépare toujours un seul élément des autres. Cela entraînera des tailles de tableau de N – 1, N – 2, N – 3, …, 1 à chaque itération où la procédure de partition sera invoquée. Calculons la complexité temporelle totale pour ce scénario en utilisant la formule de la somme pour la progression arithmétique.

T(N) = O(N) + O(N – 1) + O(N – 2) + O(N – 3) + … + O(1) = O(N * (N + 1) / 2) = O(N²)

Par conséquent, nous obtenons une complexité temporelle quadratique. C’est le pire cas possible pour le tri rapide. Malgré cela, la probabilité de ce scénario est très faible.

En moyenne, le tri rapide fonctionne en temps O(N * logN) et surpasse les autres algorithmes de tri.

Imaginez que vous développiez un système qui utilise un algorithme de tri rapide en interne. Ce ne serait pas une bonne idée de toujours choisir un élément pivot, selon le même principe (dans notre exemple, nous avons constamment choisi l’élément de fin du tableau). Si quelqu’un découvre la stratégie de choix d’un élément pivot dans le système, alors cette personne peut expressément entrer des tableaux qui donneront lieu aux pires scénarios de partition et, par conséquent, à une complexité temporelle O(N²). Cela pourrait diminuer significativement l’efficacité du système. C’est pourquoi il est toujours préférable de choisir les pivots de différentes manières à chaque itération. L’une des manières les plus populaires de le faire est de choisir un pivot au hasard.

Conclusion

Nous avons étudié le tri rapide – un algorithme bien connu pour le tri. Malgré sa complexité quadratique dans le pire scénario, il est généralement plus performant en pratique, par rapport à d’autres algorithmes tels que le tri fusion ou le tri par tas, surtout dans le cas de grands tableaux.

Toutes les images, sauf indication contraire, sont de l’auteur

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!