Python >> Tutoriel Python >  >> Python

L'algorithme de tri rapide le plus court en Python

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 algorithmes qui ne traitent pas de l'algorithme Quicksort.

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 !

Pendant que vous lisez le court article, n'hésitez pas à lire la vidéo explicative suivante où je vais vous guider à travers le code :

Passons maintenant à l'algorithme Quicksort !

Version longue rapide

Si vous recherchez simplement le code tout de suite, je vous suggère de copier et coller le code suivant, une implémentation concise et efficace de Quicksort sans toutes les fioritures :

def quicksort(my_list):
    # recursion base case - empty list
    if not my_list:
        return []

    # first element is pivot
    pivot = my_list[0]

    # break up problem
    smaller = [x for x in my_list[1:] if x < pivot]
    greater = [x for x in my_list[1:] if x >= pivot]

    # recursively solve problem and recombine solutions
    return quicksort(smaller) + [pivot] + quicksort(greater)


print(quicksort([4, 4, 3, 2, 1, 8, 9]))
# [1, 2, 3, 4, 4, 8, 9]

print(quicksort(['Alice', 'Carl', 'Bob']))
# ['Alice', 'Bob', 'Carl']

L'article restant plongera dans le code et vous fournira une compréhension supplémentaire de l'algorithme.

Idée d'algorithme de tri rapide

Quicksort trie une liste en divisant récursivement le gros problème (trier une grande liste ) en petits problèmes (tri de deux petites listes ) 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".

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 :(1) trier la partition de droite et (2) trier la partition de 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 :

Plongeons-nous dans le code - une simple solution en une seule ligne fera l'affaire ! 🙂

Code Python de tri rapide

Formulation du problème :Créer une fonction q qui implémente l'algorithme Quicksort dans une seule ligne de code Python en triant et en renvoyant tout argument spécifié sous la forme d'une liste d'entiers.

Solution  :La solution à une ligne suivante pour l'algorithme Quicksort utilise la récursivité pour résoudre ce problème.

## The Data
unsorted = [33, 2, 3, 45, 6, 54, 33]


## The Quicksort 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))

Comment ça marche – Explication du code de tri rapide

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 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 de manière triviale).

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 (left et right ) selon qu'ils sont plus petits ou plus grands que le pivot. Pour ce faire, nous utilisons la compréhension de liste simple. Vous pouvez regarder notre vidéo explicative si vous avez besoin d'un bref rappel :

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]

Résumé Instagram Quicksort

Si vous voulez juste avoir une idée rapide de la façon de le faire en plusieurs lignes, consultez ce post Instagram (faites glisser vers la droite) :