📥 Tri par Insertion : Cours & Principes

📖 1. Définition

Le tri par insertion (Insertion Sort) est un algorithme de tri intuitif qui construit progressivement un sous-tableau trié du côté gauche en insérant un à un les éléments restants à leur place adéquate.

⚙️ 2. Principe de l’algorithme

Le fonctionnement repose sur les étapes clés suivantes :

  • Considérer que le premier élément (indice 0) est déjà trié.
  • Prendre l’élément suivant (mémorisé dans une variable val) et le comparer aux éléments de la zone triée en partant de la droite vers la gauche.
  • Décaler vers la droite les éléments supérieurs à val.
  • Insérer val à sa position libérée, puis répéter l’opération pour tous les éléments du tableau.

⚠️ Note très importante :

L’utilisation de la fonction prédéfinie en Python .sort() ou sorted() est strictement hors programme. Vous devez obligatoirement implémenter la logique itérative du décalage et de l’insertion.

📊 Simulation Visuelle & Algorithme Animé

Visualisez pas à pas l’insertion de chaque élément dans la zone triée.

📊 Espace de simulation

450ms
🤖 i
👾 j

Suivi de l’exécution (i, j, val) :

i Générez ou lancez la simulation… i
j – j
val – val

État du tableau T après chaque insertion (i) :

Étape / i Valeurs du tableau T (élément inséré en évidence)
Initial –

Algorithme & TDOL :

Procédure Tri_Insertion(@T: Tab, n: Entier)
Début
    Pour i de 1 à n-1 Faire
        val ← T[i]
        j ← i - 1
        Tant que (j ≥ 0) Et (T[j] > val) Faire
            T[j+1] ← T[j]
            j ← j - 1
        FinTantQue
        T[j+1] ← val
    FinPour
Fin

TDOL

Objet Type
i, j, val Entier

💻 Traduction en Python

def tri_insertion(T, n):
    for i in range(1, n):
        val = T[i]
        j = i - 1
        while j >= 0 and T[j] > val:
            T[j + 1] = T[j]
            j -= 1
        T[j + 1] = val

📝 3. Exercice d’application

Situation : Lors d’une compétition de tir à l’arc, les scores successifs des archers sont enregistrés au fur et à mesure de leur arrivée. Pour maintenir le tableau des scores constamment trié par ordre croissant, les juges insèrent chaque nouveau score à sa position exacte parmi les précédents (méthode du tri par insertion).

Écrire un programme modulaire permettant de :

  • Saisir le nombre de compétiteurs N (compris entre 2 et 50).
  • Remplir le tableau avec les scores.
  • Trier les scores par ordre croissant à l’aide de la procédure du tri par insertion.
  • Afficher le classement final trié.

Donner la solution sous forme d’algorithme et sa traduction en programme Python.

Correction détaillée

💻 Programme Principal (Algorithme)

Algorithme Classement_Tir_Archers
DEBUT
  SaisieTaille(N)
  RemplirTableau(Scores, N)
  TriInsertion(Scores, N)
  AfficherTableau(Scores, N)
FIN

📋 Tableaux de Déclaration (TDNT & TDOG)

TDNT

Type Structure
Tab Tableau de 50 entiers

TDOG (avec les noms des procédures)

Objet Type / Nature
Scores Tab
N Entier
SaisieTaille Procédure
RemplirTableau Procédure
TriInsertion Procédure
AfficherTableau Procédure

⚙️ Liste des Modules (Procédures) et TDOL

1. Procédure SaisieTaille

Procedure SaisieTaille(@n: Entier)
DEBUT
  Répéter
    Ecrire("Donner le nombre de participants (entre 2 et 50) : ")
    Lire(n)
  Jusqu'à n dans [2..50]
FIN

TDOL : Aucun objet local.

2. Procédure RemplirTableau

Procedure RemplirTableau(@t: Tab, n: Entier)
DEBUT
  Pour i de 0 à n-1 Faire
    Ecrire("Score archer ", i+1, " : ")
    Lire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

3. Procédure TriInsertion

Procedure TriInsertion(@t: Tab, n: Entier)
DEBUT
  Pour i de 1 à n-1 Faire
    val ← t[i]
    j ← i - 1
    Tant que (j ≥ 0) Et (t[j] > val) Faire
      t[j+1] ← t[j]
      j ← j - 1
    Fin Tant que
    t[j+1] ← val
  Fin Pour
FIN

TDOL : i, j, val (Entiers)

4. Procédure AfficherTableau

Procedure AfficherTableau(t: Tab, n: Entier)
DEBUT
  Ecrire("Classement officiel des scores triés :")
  Pour i de 0 à n-1 Faire
    Ecrire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

🐍 Version Python (Traduction complète)

def saisie_taille():
    n = int(input("Nombre de participants (2-50) : "))
    while not (2 <= n <= 50):
        n = int(input("Erreur (2-50) : "))
    return n

def remplir_tableau(n):
    return [int(input(f"Score archer {i+1} : ")) for i in range(n)]

def tri_insertion(t, n):
    for i in range(1, n):
        val = t[i]
        j = i - 1
        while j >= 0 and t[j] > val:
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = val

def afficher_tableau(t):
    print("Classement officiel des scores triés :", t)

# Programme Principal
N = saisie_taille()
Scores = remplir_tableau(N)
tri_insertion(Scores, N)
afficher_tableau(Scores)