TS-CAlgorithmes de tri

Tri par insertion — contexte fichier / voisinage

Idée directrice

Le tri par insertion place chaque nouvel élément à sa place parmi les éléments déjà triés (décalages). Le devoir i-s1-01 l'utilise pour ordonner un voisinage de cases d'un tableau/matrice avant écriture fichier.

Signature de reconnaissance — l'énoncé se trahit ainsi

« trié dans l'ordre croissant »

« tri par insertion »

« groupement voisin »

Sujet principal

Exercice — dans l'esprit des sujets d'informatique

3 questionsCorrigé masqué

On doit ordonner un petit tableau de caractères (ou d'entiers) dans l'ordre croissant par le tri par insertion.

Écrire l'algorithme du tri par insertion croissante sur T[1..n].
Appliquer à T = [D, B, A, C] (indices 1..4) : montrer le tableau après l'insertion de chaque élément (passe par passe).
Comparer en une phrase le nombre de comparaisons au pire avec le tri à bulles (même ordre de grandeur).

Voir la correction commentéeAprès avoir posé votre démarche

1. Tri par insertion.

Pour i de 2 à n faire
  x ← T[i] ; j ← i-1
  TantQue (j ≥ 1) et (T[j] > x) faire
    T[j+1] ← T[j] ; j ← j-1
  FinTantQue
  T[j+1] ← x
FinPour

2. Départ [D,B,A,C].
- i=2, x=B → [B,D,A,C]
- i=3, x=A → [A,B,D,C]
- i=4, x=C → [A,B,C,D]

Le tableau est trié croissamment.

3. Au pire, insertion et bulles font $\Theta(n^2)$ comparaisons (et décalages/échanges). L'insertion est souvent meilleure sur données presque triées.

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 01

Drill TS-C.1 — trace et nombre de comparaisons du tri par insertion

2 questionsCorrigé masqué

On applique le tri par insertion croissante au tableau T = [5, 2, 4, 1] (indices 1..4).

Donner l'état du tableau après l'insertion de chaque élément.
Compter le nombre total de comparaisons T[j] > x effectuées (on compte aussi la comparaison qui échoue et arrête le décalage).

Voir la correction commentéeAprès avoir posé votre démarche

1. i=2, x=2 : 5 > 2, décalage → [2, 5, 4, 1]. i=3, x=4 : 5 > 4 décalage, 2 > 4 faux → [2, 4, 5, 1]. i=4, x=1 : 5, 4 et 2 sont tous > 1 → [1, 2, 4, 5].

2. Comparaisons : 1 (i=2, la partie triée est épuisée après le décalage) + 2 (i=3) + 3 (i=4, épuisement) = 6. Sur un tableau déjà trié il n'y en aurait que n-1 = 3 : l'insertion est d'autant plus rapide que les données sont presque ordonnées, ce qui n'est pas le cas du tri à bulles naïf.

Méthode / Automatismes

Invariant : T[1..i-1] est trié avant d'insérer T[i].
Dans le devoir i-s1-01, l'insertion sert un voisinage de cases avant stockage fichier.

Pièges classiques

Écrire un tri par sélection en l'appelant insertion ; oublier le décalage.