Tri Rapide – quicksort –

 Exercice: Tri Rapide – quicksort –

Fonction Python tri_rapide(L) qui permet de trier une liste L en utilisant l’algorithme de tri rapide (en anglais quicksort), L est une liste passée en paramètre.

Principe de Tri rapide

Le principe du tri rapide (en anglais quicksort) est de diviser (diviser pour régner) la liste en deux sous listes (deux partitionnement) telles que les éléments de la première soient inférieurs aux éléments de la seconde. On recommence jusqu’à avoir des sous-listes réduites à un seul élément.

Pour diviser la liste en deux sous-listes, on choisit une des valeurs de la liste comme pivot (ici le pivot est le dernier élément).On construit une sous-liste gauche avec les éléments dont la valeur est inférieure à celle du
pivot et une sous-liste droite avec les éléments supérieurs au pivot.

Comme on fait cette construction directement sur la liste qui représente la liste, la frontière entre les deux sous-listes donne la place définitive du pivot.

Exemple de fonctionnement: Tri rapide pour la liste  L=[ 3 , 5 , 2 , 1 , 8 , 9 , 7 , 4 ]

Ici on choisi le dernier élément comme pivot

 [ 3 , 2 , 1 ][ 4 ][5 , 8 , 9 , 7]  Le pivot=4 est bien placé à sa place définitive.

[ 1 ][3 , 2][ 4 ][5, 8 , 9 , 7 ]   Le pivot=1 est bien placé à sa place définitive.

[ 1 ][ 2 ][ 3][ 4 ][5, 8, 9, 7]   Le pivot=2 est bien placé à sa place définitive.

[ 1 ][ 2 ][ 3][ 4 ][5, 8, 9, 7]   Le pivot=3 est bien placé à sa place définitive.

[ 1 ][ 2 ][ 3][4][5][7 ][8, 9]   Le pivot=7 est bien placé à sa place définitive.

[1][2][3 ][4 ] [5 ][7 ][8 , 9]   le pivot=5 est bien placé à sa place définitive.

[1][2][3][4 ][5 ][7 ][8 ][9 ]  le pivot=9 est bien placé à sa place définitive.

[1][2][3 ][4][5 ][7 ][8 ][9 ]  le pivot=8 est bien placé à sa place définitive.

Résultat finale la liste L est bien triée [ 1, 2, 3, 4, 5, 7, 8, 9]

Exemple d’exécution:

>>> L=[4 , 2 , 1 , 8 , 7 , 5 , 3 , 6 ]
>>> tri_rapide( L )
[1, 2, 3, 4, 5, 6, 7, 8]

Partager avec...
Share on FacebookShare on Google+Tweet about this on Twitter
Tagués avec : , , , , , , , , , , , , , , , , , , , , , , , ,

Poster un Commentaire

Soyez le premier à commenter !

Utiliser [python] ... [/python] pour insérer un code Python.

$latex format_latex $ pour insérer au format latex.

Exemple:

[python]
print('Hello word')
[/python]

$latex \sqrt{x} $

Laisser un commentaire


Programme similaire