Tri par insertion

Exercice: Tri par insertion

Fonction Python tri_par_insertion( L ) qui retourne une liste L triée en utilisant l’algorithme de tri par insertion, L est une liste passée en paramètre.

Principe du tri par insertion (Tri croissant)

A l’étape i

on considéré que la liste est divisée en deux parties (deux listes L1 et L2)

  • L1 de taille i déjà triée se compose des élément d’ indices de 0 à i-1
  • L2 de taille n-i pas encore triée se compose des éléments d’indices de i jusqu’à n-1

On insert ensuite l’élément L[ i ] dans la liste L1 qui est déjà trié.
La taille de la liste L1 augmente par 1 devient i+1 et celle de L2 diminue par 1 devient n-i-1.
On répéte la procédure juqu’à que  la taille de  L1=n et la taille de L2=0

Exemple d’exécution:

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

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