Algorithme de tri par insertion

On présente un algorithme ayant les spécifications suivantes :

E : L, Liste.

S : L triée.

Principe :

• Cette procédure compare le second élément d’une liste, L entré en paramètre, avec le premier élément de cette liste et échange de place si le second élément est inférieur au premier.

• Elle effectue la même manipulation avec les éléments suivants en les comparant chacun à chaque éléments qui les précèdent.

Algorithme de tri par insertion

Spécification:

E:L, Liste

S:L triée.

Procédure Tri_Insertion(L1 : Liste)

Var

J := 2 #Compteur boucle Pour

Clé := Element

i : int

Début

Pour j allant de 2 à n faire

Clé =L1 [j]

i = j -1

Tant que i>0 et A[i]>clé faire

L1 [i+1] =L1[i]

i= i -1

Fin Tant que

L1 [i+1] = clé

Fin Pour

Fin

Etude du temps d’exécution de l’algorithme de tri par insertion

Temps d'execution

On présente un algorithme ayant les spécifications suivantes :

E : L, Liste.

S : L triée.

Principe :

• Cette procédure compare le second élément d’une liste, L entré en paramètre, avec le premier élément de cette liste et échange de place si le second élément est inférieur au premier.

• Elle effectue la même manipulation avec les éléments suivants en les comparant chacun à chaque éléments qui les précèdent.

Algorithme de tri par insertion

Spécification:

E:L, Liste

S:L triée.

Procédure Tri_Insertion(L1 : Liste)

Var

J := 2 #Compteur boucle Pour

Clé := Element

i : int

Début

Pour j allant de 2 à n faire

Clé =L1 [j]

i = j -1

Tant que i>0 et A[i]>clé faire

L1 [i+1] =L1[i]

i= i -1

Fin Tant que

L1 [i+1] = clé

Fin Pour

Fin

Etude du temps d’exécution de l’algorithme de tri par insertion

Temps d'execution

...