Accueil › Cours › Les tris

Les leçons de ce chapitre

1. Le tri à bulles
2. Le tri par sélection
3. Le tri par insertion

Leçon 14.1 : Le tri à bulles

10 min

Trier un tableau, c'est ranger ses éléments dans l'ordre croissant (du plus petit au plus grand) ou décroissant. Le tri à bulles compare chaque élément avec son voisin : s'ils sont dans le mauvais ordre, on les permute. Les grands éléments remontent vers la fin comme des bulles.

• On parcourt le tableau et on permute chaque couple mal rangé T[i] > T[i + 1].
• Une variable booléenne echange retient s'il y a eu au moins une permutation.
• On recommence tant qu'il y a eu un échange : Répéter … Jusqu'à echange = Faux.

Pour permuter deux cases, on passe par une variable auxiliaire : aux ← T[i], T[i] ← T[i + 1], T[i + 1] ← aux.

Astuce : En Python, Répéter s'écrit avec while et la variable echange mise à True avant la boucle. Pas besoin de break.

En Python

On lit 5 entiers, on les trie avec le tri à bulles, puis on les affiche un par ligne.

n = 5
t = [0] * n
for i in range(n):
    t[i] = int(input())
echange = True
while echange:
    echange = False
    for i in range(n - 1):
        if t[i] > t[i + 1]:
            aux = t[i]
            t[i] = t[i + 1]
            t[i + 1] = aux
            echange = True
for i in range(n):
    print(t[i])

En algorithme

La même idée en algorithme, avec Répéter … Jusqu'à.

Algorithme TriBulles
Début
  n ← 5
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Répéter
    echange ← Faux
    Pour i de 1 à n - 1 Faire
      Si T[i] > T[i + 1] Alors
        aux ← T[i]
        T[i] ← T[i + 1]
        T[i + 1] ← aux
        echange ← Vrai
      FinSi
    FinPour
  Jusqu'à echange = Faux
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
n, i, aux | Entier
T | Tableau de 5 Entiers
echange | Booléen

Leçon 14.2 : Le tri par sélection

10 min

Le tri par sélection cherche le plus petit élément du tableau et le met à la première place. Puis il cherche le plus petit parmi les restants et le met à la deuxième place, et ainsi de suite.

• Pour chaque position i de la première à l'avant-dernière :
• chercher la position pmin du minimum entre i et la fin ;
• si pmin ≠ i, permuter T[i] et T[pmin].

Astuce : Avec n éléments, il y a toujours n − 1 tours, et au plus une permutation par tour.

Attention : On retient la position du minimum (pmin), pas seulement sa valeur : sinon on ne sait pas quelle case permuter.

En Python

Cinq notes lues, triées par sélection, puis affichées.

n = 5
t = [0] * n
for i in range(n):
    t[i] = int(input())
for i in range(n - 1):
    pmin = i
    for j in range(i + 1, n):
        if t[j] < t[pmin]:
            pmin = j
    if pmin != i:
        aux = t[i]
        t[i] = t[pmin]
        t[pmin] = aux
for i in range(n):
    print(t[i])

En algorithme

Deux boucles Pour imbriquées : la première fixe la place, la seconde cherche le minimum.

Algorithme TriSelection
Début
  n ← 5
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Pour i de 1 à n - 1 Faire
    pmin ← i
    Pour j de i + 1 à n Faire
      Si T[j] < T[pmin] Alors
        pmin ← j
      FinSi
    FinPour
    Si pmin ≠ i Alors
      aux ← T[i]
      T[i] ← T[pmin]
      T[pmin] ← aux
    FinSi
  FinPour
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
n, i, j, pmin, aux | Entier
T | Tableau de 5 Entiers

Leçon 14.3 : Le tri par insertion

11 min

Le tri par insertion fait comme un joueur de cartes : il prend les éléments un par un et insère chacun à sa place parmi ceux déjà triés à sa gauche.

• Pour i de la deuxième position à la dernière : on garde v ← T[i].
• Tant que l'élément à gauche est plus grand que v, on le décale d'une case vers la droite.
• On pose v dans la case libérée.

Attention : Dans la condition j > 1 et T[j - 1] > v, le test j > 1 vient en premier : il évite de lire une case avant le début du tableau.

Astuce : Ce tri est rapide quand le tableau est presque trié : il y a peu de décalages.

En Python

En Python, la première case est 0, donc la condition devient j > 0.

n = 5
t = [0] * n
for i in range(n):
    t[i] = int(input())
for i in range(1, n):
    v = t[i]
    j = i
    while j > 0 and t[j - 1] > v:
        t[j] = t[j - 1]
        j = j - 1
    t[j] = v
for i in range(n):
    print(t[i])

En algorithme

Une boucle Pour pour chaque élément, une boucle Tant que pour les décalages.

Algorithme TriInsertion
Début
  n ← 5
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Pour i de 2 à n Faire
    v ← T[i]
    j ← i
    Tant que (j > 1) et (T[j - 1] > v) Faire
      T[j] ← T[j - 1]
      j ← j - 1
    FinTantQue
    T[j] ← v
  FinPour
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
n, i, j, v | Entier
T | Tableau de 5 Entiers

S'entraîner gratuitement

Chaque leçon a 3 exercices gratuits avec indices pour appliquer ce chapitre avec Hannibot.

← Chapitre précédent : Le choix multiple : Selon · Chapitre suivant : La recherche dans un tableau →

Tous les chapitres · Voir les devoirs corrigés de 2ème TI

Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.