Tri rapide
Quicksort est un algorithme de tri qui est utilisé pour trier les éléments d'un tableau. Il a été créé par Tony Hoare en 1959, et il est toujours largement utilisé aujourd'hui. Quicksort crée des partitions dans le tableau, ce qui signifie essentiellement qu'il divise le tableau en deux parties, puis continue à diviser ces parties en d'autres parties, et à trier en cours de route. Il effectue le tri réel par nature, car il s'agit d'un tri de comparaison. Cela signifie qu'il choisit un point de pivot dans le tableau et le compare ensuite à tous les autres points du tableau.
Visualisation animée de l'algorithme de quicksort. Les lignes horizontales sont des valeurs de pivot
Algorithme
- Choisissez n'importe quel élément dans le tableau, ce sera maintenant le point de pivot.
- Partagez les éléments. Comparez tous les éléments du tableau au pivot, ceux qui sont plus bas que le pivot sont déplacés à gauche du pivot, et tous les éléments du tableau qui sont plus hauts que le pivot sont déplacés à droite du pivot. Notez que notre pivot est maintenant dans sa position triée.
- Rentrer dans les deux partitions. Appliquez les deux étapes ci-dessus aux deux partitions que nous avons créées à l'étape 2.
Souvent, l'élément le plus à gauche est choisi comme pivot. La récursion signifie que l'algorithme exécute le même algorithme exact sur les deux partitions qui ont été créées par les comparaisons avec le pivot. Notez que cet algorithme continuera à partitionner le tableau en sous-réseaux, et à diviser ces sous-réseaux en sous-réseaux encore plus petits. Chaque fois qu'il fait cela, il choisira un nouveau pivot dans le sous-réseau et comparera les éléments au sous-réseau. Le cas de base est lorsque l'algorithme atteint un sous-réseau avec un seul élément, dans lequel il s'arrête simplement parce qu'un élément n'a pas besoin d'être trié.
