Algorithme de tri par insertion

1 Preuves de correction

Exercice 1.

Montrer rigoureusement la correction de l’algorithme de tri par insertion vu à la fin du dernier cours :

on prouvera un invariant pour chaque boucle. Donner le pire et le meilleur cas pour la complexité et

évaluer cette complexité dans les deux cas.

Lorsque l’on a une boucle Pour i de 1 à n, on sait qu’elle sera exécutée exactement n fois : au bout

de n itérations, la boucle se termine. En revanche, ce n’est nullement le cas des boucles Tant que qui

continuent tant que la condition est vérifiée. Il se peut qu’on entre dans une boucle infinie (condition

toujours vraie), et dans les cas qui nous intéressent il n’est pas toujours aisé de montrer que ce genre

de boucle termine. Par exemple, on ne sait pas montrer que la boucle suivante termine pour tout a

(problème de Syracuse) :

x <- a

Tant que (x > 1) faire

Si x est pair, x <- x/2

Sinon x <- 3*x+1

La méthode standard pour montrer qu’une boucle Tant que termine est de montrer qu’il existe une

quantité (typiquement un entier positif) qui décroît à chaque itération : dans ce cas, la boucle s’arrête

dès que l’entier devient nul car il ne peut plus décroître. Par exemple, dans la boucle suivante :

S : tableau d’entiers

x <- a

y <- b

Tant que (x > 0 et y > 0) faire

Si S[x] est pair alors x <- x-1

Sinon y <- y-1

c’est la quantité x+y qui décroît à chaque étape. Puisque la condition x>0 et y>0 impose que la somme

soit positive, on en déduit que la boucle termine (en au plus a + b itérations).

Exercice 2.

On se donne un tableau S d’entiers triés par ordre croissant et un entier cible x. Proposer un algorithme

linéaire pour trouver s’il existe deux éléments de S dont la somme vaut x. Prouver que la boucle termine

(quelle quantité décroît à chaque itération ?) et que votre algorithme est correct (en montrant un

invariant).

2 Tri fusion

On rappelle le principe du tri fusion d’un tableau A : on coupe le tableau A au milieu, de façon à

avoir les deux moitiés A1 et A2. On trie récursivement A1 et A2, puis on fusionne les deux moitiés de

manière à ce que le tableau A entier soit trié.

On appellera Fusion(A1,A2,A) la procédure qui fusionne les deux tableaux A1 et A2 dans A. On a

donc un algorithme de la forme :

1

Tri_fusion(A) :

Si A a un seul élément, sortir

Recopier A[1..n/2] dans A1

Recopier A[n/2+1..n] dans A2

Tri_fusion(A1)

Tri_fusion(A2)

Fusion(A1,A2,A)

Exercice 3.

Proposer un algorithme linéaire pour la procédure de fusion. Prouver que cet algorithme est correct,

c’est-à-dire

...