Vidéo: Sorting Algorithm | Quick Sort - step by step guide 2024
Vous découvrirez ici comment fonctionne l'une des techniques de tri les plus utilisées en Java. Cette technique est appelée Quicksort, et c'est une utilisation très ingénieuse de la récursivité.
Pour la plupart d'entre nous, comprendre comment les algorithmes de tri tels que Quicksort fonctionnent n'est qu'un exercice intellectuel. L'API Java a déjà intégré le tri.
La technique Quicksort trie un tableau de valeurs en utilisant la récursivité. Ses étapes de base sont donc:
-
Choisissez une valeur arbitraire comprise dans la plage de valeurs du tableau.
Cette valeur correspond au point de pivot . La façon la plus courante de choisir le point de pivot est de simplement choisir la première valeur dans le tableau. Les gens ont écrit des diplômes de doctorat sur des façons plus sophistiquées de choisir un point de pivot qui résulte en un tri plus rapide. Stick avec l'utilisation du premier élément dans le tableau.
-
Réorganisez les valeurs dans le tableau de sorte que toutes les valeurs inférieures au point de pivot se trouvent sur le côté gauche du tableau et que toutes les valeurs supérieures ou égales au point de pivot se trouvent du côté droit du tableau. tableau.
La valeur de pivot indique la limite entre le côté gauche et le côté droit de la matrice. Ce ne sera probablement pas le point mort, mais cela n'a pas d'importance. Cette étape est appelée partitionnement, et les côtés gauche et droit des tableaux sont des partitions .
-
Traitez maintenant chacune des deux sections du tableau comme un tableau séparé, et recommencez avec l'étape 1 pour cette section.
C'est la partie récursive de l'algorithme.
La partie la plus difficile de l'algorithme Quicksort est l'étape de partitionnement, qui doit réorganiser la partition de sorte que toutes les valeurs inférieures au point de pivotement soient à gauche et tous les éléments plus grands que le pivot le point est sur la droite. Supposons que le tableau a ces dix valeurs:
38 17 58 22 69 31 88 28 86 12
Ici le point de pivot est 38, et la tâche de partitionnement est de réorganiser le tableau à quelque chose comme ceci: < 17 12 22 28 31 38 88 69 86 58
Notez que les valeurs sont toujours hors service. Le tableau, cependant, a été divisé autour de la valeur 38: Toutes les valeurs qui sont inférieures à 38 sont à gauche de 38, et toutes les valeurs supérieures à 38 sont à droite de 38.
Maintenant, vous pouvez diviser le tableau en deux partitions à la valeur 38 et répétez le processus pour chaque côté. La valeur de pivot elle-même va avec la partition de gauche, donc la partition de gauche est la suivante:
17 12 22 28 31 38
Cette fois, l'étape de partitionnement choisit 17 comme point de pivot et réorganise les éléments comme suit: > 12 17 22 28 31 38
Comme vous pouvez le voir, cette partie du tableau est maintenant triée.Malheureusement, Quicksort ne réalise pas cela à ce stade, donc il faut un peu plus de récursions pour être sûr. Mais c'est le processus de base.
