TS-AAlgorithmes de tri

Algorithmes de tri — sélection, insertion, bulles

Idée directrice

L'énoncé présente un tableau non trié et demande d'écrire un ou plusieurs algorithmes de tri (sélection, insertion ou bulles), puis de donner la trace d'exécution état par état. La compréhension du rôle de chaque passe et la comparaison des complexités $O(n^2)$ sont les points clés.

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

« Écrire l'algorithme du tri par sélection » ; « Donner l'état du tableau après chaque passe du tri à bulles » ; « Combien d'échanges sont effectués lors du tri … » ; « Comparer la complexité du tri par sélection et du tri à bulles »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

Soit le tableau `T = [64, 25, 12, 22, 11]` (indices 1 à 5).

Tri par sélection. Écrire l'algorithme du tri par sélection croissante.
1. Donner l'état du tableau après chaque passe.
2. Combien d'échanges sont effectués au total ?
Tri à bulles. Écrire l'algorithme du tri à bulles avec optimisation (arrêt si aucun échange lors d'une passe).
1. Donner la trace complète (état après chaque passe).
2. Combien de passes sont nécessaires ?
Quelle est la complexité dans le pire cas de chacun de ces algorithmes ? Justifier.

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

1. Tri par sélection sur `T = [64, 25, 12, 22, 11]` (indices 1 à 5).

TDOL : `i`, `j`, `indMin`, `temp` : entier. Type/Nature : compteurs de passe, indice du minimum, temporaire d'échange.

```
DEF PROC TriSelection(var T : tableau ; N : entier)
Variables i, j, indMin, temp : entier
Début
Pour i de 1 à N-1 faire
indMin ← i
Pour j de i+1 à N faire
Si T[j] < T[indMin] alors indMin ← j FinSi
FinPour
Si indMin ≠ i alors
temp ← T[i] ; T[i] ← T[indMin] ; T[indMin] ← temp
FinSi
FinPour
Fin
```

Trace :

Passe 1 : min=11 (pos 5) ↔ pos 1 → `[11, 25, 12, 22, 64]`
Passe 2 : min=12 (pos 3) ↔ pos 2 → `[11, 12, 25, 22, 64]`
Passe 3 : min=22 (pos 4) ↔ pos 3 → `[11, 12, 22, 25, 64]`
Passe 4 : déjà ordonné sur le reste → `[11, 12, 22, 25, 64]`

T contient "11, 12, 22, 25, 64" à la fin.

2. Tri à bulles avec optimisation (arrêt si aucun échange).

```
DEF PROC TriBulles(var T : tableau ; N : entier)
Variables i, j, temp : entier ; echange : booléen
Début
echange ← Vrai ; i ← 1
TantQue (echange = Vrai) et (i ≤ N-1) faire
echange ← Faux
Pour j de 1 à N-i faire
Si T[j] > T[j+1] alors
temp ← T[j] ; T[j] ← T[j+1] ; T[j+1] ← temp
echange ← Vrai
FinSi
FinPour
i ← i + 1
FinTantQue
Fin
```

3. Complexité. Pire cas : $\dfrac{N(N-1)}{2}$ comparaisons → $O(N^2)$ pour sélection et bulles. Indices i dans [1..N-1].

Équivalent Python (extrait).
```python
def tri_selection(T):
N = len(T)
for i in range(N-1):
ind_min = i
for j in range(i+1, N):
if T[j] < T[ind_min]:
ind_min = j
T[i], T[ind_min] = T[ind_min], T[i]
return T
print(tri_selection([64,25,12,22,11]))
```

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

Entraînement 01 / 06

Drill TS-A.1 — tri par sélection

1 questionCorrigé masqué

Décrire le principe du tri par sélection d'un tableau croissant.

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

TDOL : `i`, `j`, `indMin`, `temp`. Type/Nature : indices.

```
DEF PROC TriSelection(var T : tableau ; n : entier)
Variables i, j, indMin, temp : entier
Début
Pour i de 1 à n-1 faire
indMin ← i
Pour j de i+1 à n faire
Si T[j] < T[indMin] alors indMin ← j FinSi
FinPour
{ échange T[i] ↔ T[indMin] }
FinPour
Fin
```

Min du reste puis échange ; $O(n^2)$ ; i dans [1..n-1].

Entraînement 02 / 06

Drill TS-A.2 — tri par insertion

1 questionCorrigé masqué

Décrire le principe du tri par insertion.

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

TDOL : `i`, `j`, `x`. Type/Nature : clé à insérer.

```
DEF PROC TriInsertion(var T : tableau ; n : entier)
Variables i, j, x : entier
Début
Pour i de 2 à n faire
x ← T[i] ; j ← i
TantQue (j > 1) et (T[j-1] > x) faire
T[j] ← T[j-1] ; j ← j-1
FinTantQue
T[j] ← x
FinPour
Fin
```

Insertion dans la partie triée ; i dans [2..n].

Entraînement 03 / 06

Drill TS-A.3 — tri à bulles

1 questionCorrigé masqué

Décrire le tri à bulles et son critère d'arrêt anticipé.

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

TDOL : `j`, `temp` ; `echange` booléen. Type/Nature : flag d'arrêt.

```
DEF PROC TriBulles(var T : tableau ; n : entier)
Variables j, temp : entier ; echange : booléen
Début
Répéter
echange ← Faux
Pour j de 1 à n-1 faire
Si T[j] > T[j+1] alors
temp ← T[j] ; T[j] ← T[j+1] ; T[j+1] ← temp
echange ← Vrai
FinSi
FinPour
Jusqu'à (echange = Faux)
Fin
```

Échanges de voisins ; j dans [1..n-1].

Entraînement 04 / 06

Drill TS-A.4 — complexité des tris simples

1 questionCorrigé masqué

Quelle est la complexité au pire des tris par sélection, insertion et à bulles ?

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

Sélection, insertion et bulles : complexité au pire $O(n^2)$ .

TDOL : `i`, `c` entiers. Type/Nature : compteur de comparaisons.

```
DEF FN NbComparaisonsSelection(n : entier) : entier
Variables i, c : entier
Début
c ← 0
Pour i de 1 à n-1 faire c ← c + (n-i) FinPour
Retourner c
Fin
```

On retourne $n(n-1)/2$ ; i dans [1..n-1].

Entraînement 05 / 06

Drill TS-A.5 — nombre de comparaisons (sélection)

1 questionCorrigé masqué

Combien de comparaisons effectue le tri par sélection sur un tableau de n éléments ?

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

TDOL : `n` entier. Type/Nature : taille.

```
DEF FN NbComp(n : entier) : entier
Début
Retourner n*(n-1)/2
Fin
```

On retourne $n(n-1)/2$ comparaisons (sélection) ; n dans [1..+∞[.

Entraînement 06 / 06

Drill TS-A.6 — tri décroissant

1 questionCorrigé masqué

Comment adapter un tri croissant pour obtenir un tableau décroissant ?

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

Inverser la comparaison (max au lieu de min). TDOL : `i`, `j`, `indMax`, `temp`. Type/Nature : indices.

```
DEF PROC TriSelectionDec(var T : tableau ; n : entier)
Variables i, j, indMax, temp : entier
Début
Pour i de 1 à n-1 faire
indMax ← i
Pour j de i+1 à n faire
Si T[j] > T[indMax] alors indMax ← j FinSi
FinPour
{ échange T[i] ↔ T[indMax] }
FinPour
Fin
```

i dans [1..n-1].

Méthode / Automatismes

Tri sélection : double boucle — boucle externe i (position à remplir), boucle interne j (recherche du min/max).
Tri bulles : comparer T[j] et T[j+1] ; utiliser une variable booléenne `echange` pour l'optimisation.
Trace : donner l'état complet du tableau après chaque passe (et non après chaque comparaison).
Nombre de comparaisons pire cas : $n(n-1)/2$ → $O(n^2)$ pour sélection et bulles.
Échange de deux éléments : utiliser une variable temporaire `temp`.

Pièges classiques

Pièges fréquents : oublier la variable `temp` lors de l'échange (les deux cases auraient la même valeur) ; mal borner les boucles (dépasser les indices) ; oublier l'initialisation `indMin ← i` à chaque passe dans le tri par sélection ; confondre tri croissant et décroissant (inverser le sens de comparaison).

Variantes rencontrées : tri par insertion ; tri d'un tableau de chaînes par ordre lexicographique ; tri d'un tableau de structures selon un champ donné.