Dans ce didacticiel en une seule ligne, vous découvrirez l'algorithme de tri populaire Quicksort. Étonnamment, une seule ligne de code Python suffit pour écrire l'algorithme Quicksort !
Problème :Soit une liste de valeurs numériques (entier ou flottant). Triez la liste en une seule ligne de code Python à l'aide de l'algorithme populaire Quicksort !
Exemple :Vous avez la liste [4, 2, 1, 42, 3] . Vous souhaitez trier la liste par ordre croissant pour obtenir la nouvelle liste [1, 2, 3, 4, 42] .
Réponse courte :La solution à une ligne suivante trie la liste de manière récursive à l'aide de l'algorithme Quicksort :
q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else []
Vous pouvez l'essayer vous-même en utilisant le shell de code interactif suivant :
Maintenant, plongeons dans quelques détails !
Une introduction conceptuelle
L'introduction suivante est basée sur mon nouveau livre "Python One-Liners" (Lien Amazon) qui vous enseigne la puissance d'une seule ligne de code (utilisez-la judicieusement) !
Présentation :Quicksort n'est pas seulement une question populaire dans de nombreuses interviews de code - posées par Google, Facebook et Amazon - mais aussi un algorithme de tri pratique qui est rapide, concis et lisible. En raison de sa beauté, vous ne trouverez pas beaucoup d'introductions aux classes d'algorithmes qui ne traitent pas de l'algorithme Quicksort.
Aperçu :Quicksort trie une liste en divisant de manière récursive le gros problème (tri de la liste) en problèmes plus petits (tri de deux listes plus petites) et en combinant les solutions des petits problèmes de manière à résoudre le gros problème. Afin de résoudre chaque problème plus petit, la même stratégie est utilisée de manière récursive :les problèmes plus petits sont divisés en sous-problèmes encore plus petits, résolus séparément et combinés. En raison de cette stratégie, Quicksort appartient à la classe des algorithmes "Divide and Conquer".
Algorithme :L'idée principale de Quicksort est de sélectionner un élément pivot, puis de placer tous les éléments supérieurs ou égaux à l'élément pivot à droite et tous les éléments inférieurs à l'élément pivot à gauche. Maintenant, vous avez divisé le gros problème du tri de la liste en deux sous-problèmes plus petits :trier les partitions droite et gauche de la liste. Ce que vous faites maintenant est de répéter cette procédure de manière récursive jusqu'à ce que vous obteniez une liste avec zéro élément. Cette liste est déjà triée, donc la récursivité se termine.
La figure suivante montre l'algorithme Quicksort en action :
Figure :L'algorithme Quicksort sélectionne un élément pivot, divise la liste en (i) une sous-liste non triée avec tous les éléments inférieurs ou égaux au pivot, et (ii) une sous-liste non triée avec tous les éléments qui sont plus grands que le pivot. Ensuite, l'algorithme Quicksort est appelé récursivement sur les deux sous-listes non triées pour les trier. Dès que les sous-listes contiennent au maximum un élément, elles sont triées par définition – la récursivité se termine. À chaque niveau de récursivité, les trois sous-listes (gauche, pivot, droite) sont concaténées avant que la liste résultante ne soit transmise au niveau de récursivité supérieur.
Cela nous amène au code suivant :
Python One-Liner Quicksort [Code]
Créer une fonction q qui implémente l'algorithme Quicksort dans une seule ligne de code Python - et trie ainsi tout argument donné sous la forme d'une liste d'entiers.
## The Data unsorted = [33, 2, 3, 45, 6, 54, 33] ## The One-Liner q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## The Result print(q(unsorted))
Liste :solution en une seule ligne pour l'algorithme Quicksort utilisant la récursivité.
Quelle est la sortie de ce code ? Voyons…
Explication Quicksort One-Liner
Nous avons déjà discuté de l'algorithme récursif Quicksort ci-dessus. Le one-liner ressemble exactement à l'algorithme discuté. Tout d'abord, nous créons une nouvelle fonction lambda q qui ne prend qu'un seul argument de liste l .
La fonction lambda a la structure suivante :
lambda l: q(left) + pivot + q(right) if l else []
La fonction lambda renvoie la liste vide [] dans le cas de base de la récursivité (c'est-à-dire que la liste à trier est vide et, par conséquent, triée trivialement).
Dans tous les autres cas, il sélectionne l'élément pivot comme premier élément de la liste l , divise tous les éléments en deux sous-listes (gauche et droite) selon qu'ils sont plus petits ou plus grands que le pivot. Pour ce faire, nous utilisons la compréhension de liste simple.
Comme les deux sous-listes ne sont pas nécessairement triées, nous exécutons récursivement l'algorithme Quicksort sur celles-ci. Enfin, nous combinons les trois listes et renvoyons la liste triée. Par conséquent, le résultat est :
## The Result print(q(unsorted)) # [2, 3, 6, 33, 33, 45, 54]
Connexe :Pour une expérience interactive de ce que vous venez d'apprendre, consultez notre publication Instagram sur l'algorithme Quicksort :
Ressources associées :
- La mise en œuvre la plus courte du tri rapide
- Python une ligne X
- Pythononeliners.com
- Livre "Python One-Liners" (Lien Amazon)
- Python une ligne pour la boucle
- Python Quicksort One Line
