Pour un codeur, comprendre l'algorithme Quicksort, c'est comme connaître le secret de 42 - soit vous l'obtenez, soit vous n'appartenez pas au club. Si vous ne connaissez ni l'un ni l'autre, travaillons sur le premier !
L'algorithme Quicksort :une implémentation Python
def qsort(L):
# The empty list is sorted by default
if L == []:
return []
# Pivot is first element
pivot = L[0:1]
# Sort elements that are smaller than pivot
left = qsort([x for x in L[1:] if x < L[0]])
# Sort elements that are larger or equal than pivot
right = qsort([x for x in L[1:] if x >= L[0]])
# Concatenate the three parts to the sorted list
# assuming left and right are already sorted recursively
return left + pivot + right
print(qsort([0,33,22]))
L'algorithme est une variante de l'algorithme populaire Quicksort. La fonction qsort trie la liste. Mais pourquoi?
Explication du tri rapide
Quicksort sélectionne un élément pivot dans la liste. Dans l'extrait de code, il sélectionne le premier élément de la liste à l'aide de l'indexation, c'est-à-dire L[0] .
- Ensuite, l'algorithme déplace tous les éléments qui sont plus petits que le pivot vers la gauche.
- De même, il déplace les éléments qui sont plus grands ou égaux que le pivot vers la droite.
Ceci est répété de manière récursive pour les listes de gauche et de droite.
Supposons que vous créez une nouvelle liste comme suit. Vous mettez tous les éléments qui sont plus petits que le pivot à gauche, puis le pivot, puis tous les éléments qui sont plus grands ou égaux au pivot à droite. La liste qui en résulte semble un peu plus triée, non ? Si les deux sous-listes étaient déjà triées, la liste serait parfaitement triée. C'est là que l'appel récursif de qsort entre en jeu. Il prend en charge le problème du tri de chaque sous-liste en appliquant le même schéma de pivotement et de récursivité à la sous-liste.
Voici une explication visuelle, que j'ai préparée dans le cadre de mon livre Python One-Liners :
Tri rapide des interprètes interactifs
Vous pouvez tester ce code dans notre shell de code interactif :
Exercice :Essayez de trier une liste de chaînes. Cela fonctionne-t-il ?
Tri rapide du casse-tête de code
Voici un casse-tête de code concernant l'algorithme Quicksort qui pourrait vous plaire. Cliquez sur l'image pour le résoudre dans notre application interactive de casse-tête Finxter :
Êtes-vous un codeur maître?
Testez vos compétences maintenant !
