Fonction de tri récursif rapide en python en 5 lignes de code
Dans ce mini-tutoriel, nous allons implémenter le tri récursif rapide en langage python.
Ne vous inquiétez pas, pour chaque ligne de code, je prendrai soin d’expliquer du mieux que je peux.
NB : Ce tutoriel est destiné aux programmeurs en général et non aux développeurs python en particulier, que vous soyez dans la pile python ou non.
Bon, qu’est-ce que le tri rapide ?
Le tri rapide est un algorithme de tri d’éléments (de tailles comparables) qui a été inventé en 1961 par l’informaticien Charles Hoare. C’est un algorithme basé sur le principe de partitionnement d’un vecteur (un tableau ou une liste).
Le principe est assez simple, on choisit un indice du vecteur qui va représenter le pivot tout au long de l’exécution de l’algorithme.
De manière récursive, en parcourant le vecteur de gauche à droite à partir du pivot (respectivement de droite à gauche comme illustré sur la figure), on teste si l’élément courant est supérieur ou inférieur au pivot. S’il est inférieur (respectivement supérieur), nous nous assurons que le pivot est plus à droit que lui, sinon nous échangeons le pivot et ce dernier. Plutôt simple, n’est-ce pas ?
Il est temps de créer cette fonction de tri rapide. Elle ne prend que 5 lignes de code. C’est très simple.
Tout d’abord, ouvrez votre éditeur de code préféré, et créez un fichier nommé tri_rapide_recursif.py et ouvrez-le.
Le code complet:
def quick_sort(data: list) -> list:
if len(data) <= 1:
return data else:
return ( quick_sort([e for e in data[1:] if e <= data[0]]) + [data[0]] + quick_sort([e for e in data[1:] if e > data[0]]) )
Nous définissons une fonction quick_sort qui prend une liste comme paramètre. quick_sort(data: list) -> list:
Dans la fonction, nous testons si la liste contient un élément ou aucun élément. Si c’est le cas, nous retournons la liste. Car une liste vide ou qui contient un élément est déjà triée. iflen(data) <= 1: return data
Si la liste comporte plus d’un élément :
on appelle récursivement la fonction quick_sort et on lui passe en paramètre une instruction qui retourne ou pas, une liste d’élément inférieur à l’élément d’indice 0 [e for e in data[1:] if e <= data[0]]
Et de manière similaire, on appelle récursivement quick_sort,et on lui passe en paramètre une instruction qui retourne ou pas, une liste d’éléments supérieurs à l’élément d’indice 0 [e for e in data[1:] if e > data[0]]
puis nous concaténons toutes les partitions pour retourner des listes triées
return (quick_sort([e for e in data[1:] if e <=data[0]])+[data[0]]+quick_sort([e for e in data[1:] if e > data[0]]))
Pour tester notre fonction, nous allons définir deux listes :
nombres = [3,25,6,7,1,8] et chaines = “quick_sort”.
en faisant :
print(quick_sort(numbers))
# résultat : [1, 3, 6, 7, 8, 25]
print(quick_sort(strings))
# résultat : [‘_’, ‘c’, ‘i’, ‘k’, ‘o’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’]
Et voilà pour le tri rapide.
Bonne chance dans votre processus d’apprentissage.
