Skip to content

Tri par insertion

Algorithme imagé

Je veux trier des cartes

  • Dans ma main gauche, j'ai une carte.
  • Dans ma main droite, j'ai le reste des cartes.
  • Je déplace successivement dans ma main gauche chaque carte de la main droite en l'insérant à la bonne position pour que la main gauche soit triée.
  • A l'arrivée, ma main gauche est triée et ma main droite est vide

alt text

Autrement dit:

1. Pour i allant de 1 à n-1 faire :
2.      INSERER_BONNE_PLACE(T, i)
3. Retourner T

L'algorithme INSERER_BONNE_PLACE(T, i) place correctement l'élément \(T[i]\) dans le sous-tableau trié \(T[0..i-1]\) afin que \(T[0..i]\) soit trié et que le tableau résultat soit une permutation du tableau initial.

Prouvons la correction du tri par insertion en supposant existant et totalement correct l'algorithme INSERER_BONNE_PLACE.

FORMULATION DE L'INVARIANT

L'invariant avant l'itération \(i\) est:

  • \(T[0..i-1]\) est trié
  • \(T[0..n-1]\) est une permutation du tableau initial

INITIALISATION Si le tableau est vide ou ne contient qu'un élément, la boucle ne s'exécute pas et le tableau est inchangé. Donc l'algoritme termine correctement.

Sinon, avant de rentrer la première fois dans la boucle pour \(i=1\), \(T[0]\) est trié et T est une permutation de lui-même, donc l'invariant est vrai au début.

CONSERVATION

Supposons l'invariant vrai au début de l'itération \(i\): "\(T[0..i-1]\) est trié" (HYPOTHESE)

Nous voulons montrer qu'à l'issue de la boucle transformant \(T\) en \(T'\): - \(T'[0..i]\) est trié - \(T'[0..n-1]\) est une permutation du tableau initial

Or INSERER_BONNE_PLACE(T, i) nous l'assure justement, c'est son exacte définition.

L'invariant est donc conservé.

Terminaison L'algorithme se termine car c'est une boucle bornée sur un algorithme se terminant. A l'issue du programme, \(i=n-1\) et la conservation de l'invariant nous assure donc que \(T[0..n-1]\) sera trié, et restera une permutation du tableau initial.

Il nous faut maintenant créer l'algorithme INSERER_BONNE_PLACE.

Insérer à la bonne place

Créer l'algorithme qui permette d'insérer un élément d'un tableau à la bonne place, en considérant que le sous tableau précédent soit triés.

Par exemple pour un tableau trié jusqu'à l'indice 2 inclus, voici ce que doit donner la séquence suivante:

  1. \(T=[1, 2, 3, 1.5, 0]\)
  2. on exécute INSERER_BONNE_PLACE(T, 3)
  3. on doit avoir \(T=[1, 1.5, 2, 3, 0]\)
  4. on exécute INSERER_BONNE_PLACE(T, 4)
  5. on doit avoir \(T=[0, 1, 1.5, 2, 3]\)

Indice: On utilisera un indice j, initialement valorisé à \(j←i\) et on descendra progressivement jusqu'à trouver la bonne place en décalant les éléments vers la droite.

Solution 
# Algorithme INSERER_BONNE_PLACE(T, i)
1. a_deplacer ← T[i]
2. j ← i
3. TANT QUE j>0 et T[j-1]>a_deplacer
4.    T[j-1] ← T[j]
5.    j ← j-1
6. T[j] = a_deplacer

Nous admettrons la correction de inserer_bonne_place.

Complexité

  • Etudier la complexité de inserer_bonne_place