Comprendre et mettre en œuvre l'algorithme de tri rapide

Bonjour,

J'ai essayé de comprendre le concept d'algorithme de tri rapide, mais j'ai du mal à le comprendre et à l'appliquer. J'ai parcouru de nombreux sites, regardé des tutoriels et même tenté de l'écrire moi-même, mais il semble qu'il me manque quelque chose de critique.

Quick Sort, d'après ce que j'ai compris jusqu'à présent, est un algorithme de tri qui utilise une stratégie de division pour régner. Il choisit un élément pivot et divise le tableau en deux sous-tableaux, avec des éléments inférieurs au pivot à gauche et des éléments supérieurs au pivot à droite. Cette méthode est poursuivie sur les sous-tableaux de manière récursive jusqu'à ce que le tableau complet soit trié.

Cependant, lorsque j'essaie d'implémenter la technique en Python, cela ne fonctionne pas comme prévu. Voici ce que j'ai trouvé jusqu'à présent*:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

def quick_sort(arr): if len(arr) <= 1: return arr   pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot]   return quick_sort(left) + middle + quick_sort(right)   # Example usage my_array = [38, 27, 43, 3, 9, 82, 10] sorted_array = quick_sort(my_array) print(sorted_array)

---

Lorsque j'exécute le code avec l'exemple my_array, la sortie n'est pas triée de manière appropriée, car elle devrait être similaire avec this example. J'ai l'impression de faire une erreur avec la sélection du pivot ou la division des sous-tableaux.

Quelqu'un pourrait-il m'aider à mieux comprendre l'algorithme de tri rapide et à signaler les défauts de mon implémentation*? J'apprécierais toutes les réflexions, explications ou ajustements de code qui pourraient m'orienter sur la bonne voie.

Merci pour votre compréhension et votre aide !

Salut,

Citation:

---

Envoyé par jesse100

Lorsque j'exécute le code avec l'exemple my_array, la sortie n'est pas triée de manière appropriée, car elle devrait être similaire avec this example. J'ai l'impression de faire une erreur avec la sélection du pivot ou la division des sous-tableaux.

---

Si j'exécute votre code, ça affiche [3, 9, 10, 27, 38, 43, 82].
Et si je trie le tableau avec sorted, j'obtiens la même chose...
Pour moi le code fonctionne et n'est pas trop mal écrit.

Citation:

---

Envoyé par jesse100

Quelqu'un pourrait-il m'aider à mieux comprendre l'algorithme de tri rapide et à signaler les défauts de mon implémentation*? J'apprécierais toutes les réflexions, explications ou ajustements de code qui pourraient m'orienter sur la bonne voie.

---

Vous avez pleins d'exemples de code à lire pour voir comment d'autres ont fait (et le comparer à ce que vous avez fait).

note: l'algo du tri rapide est décrit ici sur wikipedia. Le coder en Python "à la lettre", c'est faire des permutations sur les éléments du tableau et non créer des tableaux... et écrire 2 fonctions partitionner et tri_rapide. Il n'est pas interdit de coder ça autrement et expliquer le pourquoi.


- W

Bonjour

Citation:

---

Envoyé par jesse100

Quick Sort, d'après ce que j'ai compris jusqu'à présent, est un algorithme de tri qui utilise une stratégie de division pour régner. Il choisit un élément pivot et divise le tableau en deux sous-tableaux, avec des éléments inférieurs au pivot à gauche et des éléments supérieurs au pivot à droite. Cette méthode est poursuivie sur les sous-tableaux de manière récursive jusqu'à ce que le tableau complet soit trié.

---

Exact.

Citation:

---

Envoyé par jesse100

Quelqu'un pourrait-il m'aider à mieux comprendre l'algorithme de tri rapide et à signaler les défauts de mon implémentation*? J'apprécierais toutes les réflexions, explications ou ajustements de code qui pourraient m'orienter sur la bonne voie.

---

Je vois pas l'utilité du tableau "milieu". Tu peux très bien avoir effectivement n éléments identiques au pivot, mais si tu décides de les considérer plus petit (ou plus grand) cela ne change pas le résultat. Et tu passes alors de 3 tests à un seul (plus petit que pivot oui/non)

Après, pour comprendre, il te suffit de prendre un papier et un crayon. Mais je vais réordonner ton exemple en 27, 38, 82, 9, 43, 10, 3
Et de là je vais choisir systématiquement le premier comme pivot (on verra mieux). D'ailleurs en fait, rien ne t'oblige à prendre le pivot au milieu du tableau. En prenant systémtiquement le premier ça ne change rien et tu gagnes un calcul.
Donc avec 27 comme pivot, tous les plus petits vont à gauche, et tous les plus gros à droite. Ca donne [9, 10, 3] à gauche, [27 pivot] et [38, 82, 43] à droite
Puis le tableau 9 10 3 devient [3], [9 pivot] et [10] (puisqu'on a là encore pris le premier comme pivot).
Et le tableau 38, 82, 43 devient [], [38 pivot] et [82, 43]. Et enfin le tableau [82, 43] devient [43] [82 pivot] et []

Puis ne reste qu'à récupérer les tableaux en repartant du haut.
Premier tableau 9 10 3 qui a donné [3] [9 pivot] et [10]. Lui c'est terminé. Ensuite on prend le pivot 27. Ca donne 3 9 10 27
Puis le tableau de droite 38 82 43 qui se subdivise en "sous-tableau gauche" (vide) puis pivot (38) puis "sous tableau droite" (43 82). Donc puisque gauche est vide, rien à faire. Puis pivot 38. Ca donne 3 9 10 27 38
Ensuite le sous-tableau droite donne "sous-sous tableau de gauche" (43) puis 82 (pivot) puis "sous-sous tableau droite" (vide). On a donc au final 3 9 10 27 38 43 82 et c'est fini.

Bonjour

Il y a quelques années, je m'étais penché sur ce sujet, et j'avais fait ce code. Il colle assez à la définition et je n'ai pas cherché à l'optimiser plus.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

def trirapide(L): """Tri rapide (quicksort) de la liste L     """ def trirap(L, g, d): pivot = L[(g+d)//2] i, j = g, d while True: while L[i]<pivot: i+=1 while L[j]>pivot: j-=1 if i>j: break if i<j: L[i], L[j] = L[j], L[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g, d = 0, len(L)-1 trirap(L,g,d)

---

Après, il faut bien sûr vérifier qu'il fait bien le boulot, y compris en terme de rapidité:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

import random import time   # fabrication d'une liste de nmax valeurs aléatoires nmax=1000000 L=[] for i in range(0, nmax): L.append(random.randint(1000000,9999999))   # tri avec mesure du temps passé tps = time.perf_counter() trirapide(L) tps = time.perf_counter()-tps   # vérification que le tri est correct et affichage si erreurs for i in range(1, nmax): if L[i]<L[i-1]: print("erreur index ",i, L[i])   # affichage de la liste triée, limité aux premières et dernières valeurs for i in range(1,100): print(L[i]) print() for i in range(len(L)-100, nmax): print(L[i])   print()

---

Tel que, chez moi, une liste de 1 millions de valeurs entières est triée en 1,5 seconde: manifestement, ça marche!

Comme amélioration, on pourrait introduire un argument optionnel comme le "key" du ".sort" de Python, afin de pouvoir trier une liste composée d'objets complexes (sous-liste, dictionnaires, etc...). On peut aussi faire une version particulière qui, au lieu de trier les valeurs, crée une liste d'index pour retrouver les valeurs triée sans modifier la liste.

Cependant, un fois qu'on a fait ça pour étudier, il faut revenir au tri "normal" de Python, qui est 10 fois plus rapide sur le même exemple (probablement parce qu'il est écrit en C). Ce tri prédéfini de Python n'est pas le tri rapide de Hoare, mais le TimSort" de Tim Peters (https://fr.wikipedia.org/wiki/Timsort). Ce tri a un gros avantage: il est "stable", c'est à dire qu'il ne modifie pas l'ordre des éléments déjà au bon endroit. Cela permet de faire facilement du tri multicritère.

Citation:

---

Envoyé par tyrtamos

Cependant, un fois qu'on a fait ça pour étudier

---

Un algorithme s'étudie souvent en essayant de comprendre ce qu'il se passe pas à pas. Papier, crayon sont les outils à privilégier pour visualiser les états de chaque étape. Avec l'habitude, on pourra faire "sans".

Traduire la chose en Python est une autre gymnastique: on essaie de trouver structures de données (ici, c'est facile) et mise en forme des itérations appropriées pour retrouver/relire facilement l'algorithme qu'on cherche à coder.

Arrivé là, on peut retravailler son "python"...

Si on s'attache à ne pas griller les étapes, c'est un très bon exercice qui n'a d'autre utilité qu'à s'entraîner (le tri standard étant bien plus performant).

- W

@wiztricks => entièrement d'accord!

Petit complément pour le fun: ajout de l'argument "key" comme pour le ".sort" de Python:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

def trirapide(L, key=None): """Tri rapide (quicksort) de la liste L     """ key = (lambda x:x,) if key is None else key def trirap(L, g, d): pivot = key(L[(g+d)//2]) i, j = g, d while True: while key(L[i])<pivot: i+=1 while key(L[j])>pivot: j-=1 if i>j: break if i<j: L[i], L[j] = L[j], L[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g, d = 0, len(L)-1 trirap(L,g,d)

---

Par exemple, on a une "liste de listes" avec des sous-listes de 2 valeurs (comme [452365, 789456]). On veut la trier selon la 2ème valeur (donc à l'indice 1):

Code:

---

trirapide(L, key=lambda v:v[1])

---

Au niveau rapidité, on perd un peu, bien sûr: temps de calcul multiplié par 2 pour la liste de listes prise en exemple. Avec d'autres listes, cela dépendra de la complexité des objets listés. Mais ça reste très rapide.