Table des matières:
Définition - Que signifie Quicksort?
Quicksort est un algorithme de tri populaire qui est souvent plus rapide en pratique que les autres algorithmes de tri. Il utilise une stratégie de division et de conquête pour trier rapidement les éléments de données en divisant un grand tableau en deux tableaux plus petits. Il a été développé par Charles Antony Richard Hoare (communément appelé CAR Hoare ou Tony Hoare) en 1960 pour un projet de traduction automatique pour le National Physical Laboratory.Techopedia explique Quicksort
Quicksort est un algorithme utilisé pour trier rapidement les éléments d'un tableau, quelle que soit sa taille. Il est assez évolutif et fonctionne relativement bien pour les petits et les grands ensembles de données, et est facile à mettre en œuvre avec peu de complexité en temps. Il le fait grâce à une méthode de division et de conquête qui divise un seul grand tableau en deux plus petits, puis répète ce processus pour tous les tableaux créés jusqu'à ce que le tri soit terminé.
L'algorithme de tri rapide est exécuté comme suit:
- Un point de pivot est choisi dans le tableau.
- Le tableau est réorganisé de sorte que toutes les valeurs plus petites que le pivot soient déplacées avant lui et toutes les valeurs plus grandes que le pivot soient déplacées après lui, les valeurs égalant le pivot allant dans les deux sens. Lorsque cela est fait, le pivot est dans sa position finale.
- L'étape ci-dessus est répétée pour chaque sous-tableau de valeurs plus petites ainsi que séparément pour le sous-tableau avec des valeurs plus élevées.
Cette opération est répétée jusqu'à ce que l'ensemble du tableau soit trié.
