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.
1.(b) Nombre d'échanges. Un échange par passe où indMin ≠ i : passes 1, 2 et 3 échangent, la passe 4 trouve le minimum déjà en place. Total : 3 échanges (contre 10 comparaisons).

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

2.(a) Trace du tri à bulles sur [64, 25, 12, 22, 11] :
- Passe 1 : [25, 12, 22, 11, 64] (4 échanges, le 64 remonte en fin)
- Passe 2 : [12, 22, 11, 25, 64] (3 échanges)
- Passe 3 : [12, 11, 22, 25, 64] (1 échange)
- Passe 4 : [11, 12, 22, 25, 64] (1 échange)
- Passe 5 : aucun échange → echange = Faux, arrêt.
2.(b) Il faut 4 passes utiles plus une cinquième passe de vérification qui ne modifie rien ; sans l'optimisation, l'algorithme ferait systématiquement N-1 = 4 passes.
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).

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
    Si indMin ≠ i alors
      temp ← T[i] ; T[i] ← T[indMin] ; T[indMin] ← temp
    FinSi
  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
    Si indMax ≠ i alors
      temp ← T[i] ; T[i] ← T[indMax] ; T[indMax] ← temp
    FinSi
  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é.