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 (esprit i-s1-01 : « trié … en utilisant 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 — Rôle dans le problème matrice

1 questionCorrigé masqué

Dans le problème de la synthèse i-s1-01, on forme pour chaque élément un « groupement voisin » trié croissant selon les colonnes. Quel algorithme de tri le sujet impose-t-il explicitement (parmi insertion, bulles, sélection) ? Citer le fragment de consigne.

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

Le tri par insertion (énoncé : « trié dans l'ordre croissant selon les colonnes en utilisant le tri par insertion »). Ce n'est ni le tri à bulles ni le tri par sélection. L'insertion convient bien à de petits voisinages que l'on ordonne avant écriture dans le fichier d'enregistrements.

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.