Tri par sélection

Avant de commencer

Vous avez un tas de copies à classer par note. Naturellement, vous cherchez la plus basse, vous la mettez en premier, puis la suivante, etc. C'est exactement le tri par sélection.

1. L'idée

À chaque tour i, on cherche le minimum dans la portion T[i..n] et on l'échange avec T[i]. Après n − 1 tours, le tableau est trié.

Étape 1 : [5, 2, 8, 1, 4]  →  min en pos 4 (valeur 1)  →  échange T[1] ↔ T[4]
          [1, 2, 8, 5, 4]
Étape 2 : on cherche min dans T[2..5]  →  déjà en pos 2 (valeur 2)
          [1, 2, 8, 5, 4]
Étape 3 : min dans T[3..5] = 4 (pos 5)  →  échange T[3] ↔ T[5]
          [1, 2, 4, 5, 8]
Étape 4 : min dans T[4..5] = 5  →  déjà en place
          [1, 2, 4, 5, 8]  ← trié

2. L'algorithme

DEF PROC Tri_Selection(VAR T : Tableau, n : entier)
  Pour i de 1 à n-1 Faire
    pos_min ← i
    Pour j de i+1 à n Faire
      Si T[j] < T[pos_min] Alors
        pos_min ← j
      FinSi
    FinPour
    Si pos_min ≠ i Alors
      Echanger(T[i], T[pos_min])
    FinSi
  FinPour
Fin Tri_Selection

DEF PROC Echanger(VAR a, b : entier)
  temp ← a
  a ← b
  b ← temp
Fin Echanger

DEF PROC Tri_Selection(VAR T : Tab, n : entier)
  Pour i de 1 à n-1 Faire
    pos_min ← i
    Pour j de i+1 à n Faire
      Si T[j] < T[pos_min] Alors
        pos_min ← j
      FinSi
    FinPour
    Si pos_min ≠ i Alors
      Echanger(T[i], T[pos_min])
    FinSi
  FinPour
Fin Tri_Selection

DEF PROC Echanger(VAR a, b : entier)
  temp ← a
  a ← b
  b ← temp
Fin Echanger

DEF PROC Tri_Selection(VAR T : Tab, n : entier)
  Pour i de 1 à n-1 Faire
    pos_min ← i
    Pour j de i+1 à n Faire
      Si T[j] < T[pos_min] Alors
        pos_min ← j
      FinSi
    FinPour
    Si pos_min ≠ i Alors
      Echanger(T[i], T[pos_min])
    FinSi
  FinPour
Fin Tri_Selection

PROCEDURE Echanger(VAR a, b : integer);
VAR temp : integer;
BEGIN
  temp := a;
  a := b;
  b := temp;
END;

PROCEDURE Tri_Selection(VAR T : Tab; n : integer);
VAR
  i, j, pos_min : integer;
BEGIN
  FOR i := 1 TO n - 1 DO
  BEGIN
    pos_min := i;
    FOR j := i + 1 TO n DO
      IF T[j] < T[pos_min] THEN
        pos_min := j;
    IF pos_min <> i THEN
      Echanger(T[i], T[pos_min]);
  END;
END;

3. Trace d'exécution

Sur T = [5, 2, 8, 1, 4] (n=5) :

4. Complexité

À chaque tour i, on fait n − i comparaisons. Total : (n−1) + (n−2) + … + 1 = n(n−1)/2 ≈ n²/2.

Le tri par sélection est quadratique : O(n²). Pour 1000 éléments, environ 500 000 comparaisons.

5. Exercices

PROCEDURE Tri_Decroissant(VAR T : Tab; n : integer);
VAR
  i, j, pos_max : integer;
BEGIN
  FOR i := 1 TO n - 1 DO
  BEGIN
    pos_max := i;
    FOR j := i + 1 TO n DO
      IF T[j] > T[pos_max] THEN     { > au lieu de < }
        pos_max := j;
    Echanger(T[i], T[pos_max]);
  END;
END;

PROCEDURE Tri_Selection_Compte(VAR T : Tab; n : integer; VAR nb_ech : integer);
VAR
  i, j, pos_min : integer;
BEGIN
  nb_ech := 0;
  FOR i := 1 TO n - 1 DO
  BEGIN
    pos_min := i;
    FOR j := i + 1 TO n DO
      IF T[j] < T[pos_min] THEN
        pos_min := j;
    IF pos_min <> i THEN
    BEGIN
      Echanger(T[i], T[pos_min]);
      nb_ech := nb_ech + 1;
    END;
  END;
END;

6. Erreurs fréquentes au bac

• Boucle externe Pour i de 1 à n (au lieu de n-1) : un tour de trop.
• Boucle interne Pour j de 1 à n (au lieu de i+1) : on remet en question des éléments déjà triés.
• Oublier d'utiliser pos_min pour mémoriser la position : on échange alors avec une mauvaise case.

7. Quiz