Définition - Que signifie Quicksort?
Quicksort est un algorithme de tri populaire qui est souvent plus rapide en pratique par rapport à d'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 Laboratoire national de physique.
Definir Tech explique Quicksort
Quicksort est un algorithme utilisé pour trier rapidement les éléments dans un tableau, quelle que soit la taille du tableau. Il est assez évolutif et fonctionne relativement bien pour les petits et grands ensembles de données, et est facile à mettre en œuvre avec peu de temps. Pour ce faire, il utilise 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 que toutes les valeurs plus grandes que le pivot soient déplacées après lui, avec des valeurs égales au pivot 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 et est effectuée séparément pour le sous-tableau avec des valeurs plus élevées.
Ceci est répété jusqu'à ce que le tableau entier soit trié.