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 ]




[python] ... [/python] pour insérer un code Python.
[latex] ... [/latex] pour insérer au format latex.

Exemple:

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

[latex]\sqrt{x}[/latex]


Poster un commentaire



Programmes proches

Comparaison entre les tris: Insertion, sélection, à bulles, rapide et fusion
Tri par fusion
Tri Rapide - quicksort -
Tri à bulle
Tri par insertion
Tri par sélection
Recherche dichotomique - Recherche dans une liste triée -
Triangle de Pascal
Les points cols d'une matrice
Transférer un vecteur à une dimension à une matrice à deux dimension
Transférer une matrice à deux dimension en vecteur à une dimension
Produit de deux polynôme
Les listes: Fonctions et méthodes prédéfinies
La puissance d'une matrice carrée
Une matrice neutre d'ordre n
Le produit de deux matrices
Somme de deux matrices
La matrice nulle
Nombre de schtroumpf
Le produit scalaire de deux vecteurs
Insérer un nombre dans une liste triée
Vérifier si une liste est triée
Nombre d'occurrence d'une valeur dans une liste
Chercher une valeur dans une liste non triée (Recherche séquentielle)
Remplir une liste par des zéros à l'aide de compréhension de la liste
La moyenne d'une liste
Le maximum d'une liste
Le minimum d'une liste
Saisir une liste de n valeurs
Taille d'une liste
remplir une liste par des zéros