Le tri rapide est un algorithme de tri très efficace basé sur le partitionnement dun tableau de données en plus petits tableaux. Un grand tableau est partitionné en deux tableaux dont lun contient des valeurs inférieures à la valeur spécifiée, disons pivot, en fonction de laquelle la partition est faite et un autre tableau contient des valeurs supérieures à la valeur pivot.
array puis sappelle lui-même récursivement deux fois pour trier les deux sous-tableaux résultants. Cet algorithme est assez efficace pour les ensembles de données de grande taille car sa complexité moyenne et dans le pire des cas sont respectivement O (n2).
Partition en tri rapide
La représentation animée suivante explique comment pour trouver la valeur pivot dans un tableau.
La valeur pivot divise la liste en deux parties. Et récursivement, nous trouvons le pivot pour chaque sous-liste jusquà ce que toutes les listes contiennent un seul élément.
Algorithme de tri rapide du pivot
Basé sur notre compréhension du partitionnement en tri rapide, nous allons essayez maintenant décrire un algorithme pour cela, qui est le suivant.
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
Pseudocode du pivot de tri rapide
Le pseudocode de lalgorithme ci-dessus peut être dérivé comme –
Algorithme de tri rapide
En utilisant lalgorithme de pivot récursivement, nous nous retrouvons avec des partitions possibles plus petites. Chaque partition est ensuite traitée pour un tri rapide. Nous définissons lalgorithme récursif pour le tri rapide comme suit –
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Pseudocode de tri rapide
Pour en savoir plus, voyons le pseudo-code pour un bref instant algorithme de tri –
Pour en savoir plus sur limplémentation du tri rapide dans le langage de programmation C, veuillez cliquer ici.