🎯 Tri par Sélection : Cours & Principes

📖 1. Définition

Le tri par sélection (Selection Sort) est un algorithme de tri par comparaison qui sépare le tableau en deux sous-ensembles : une partie gauche déjà triée et une partie droite non triée. Initialement, la zone triée est vide et la zone non triée occupe tout le tableau.

⚙️ 2. Principe de l’algorithme

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

  • Parcourir la sous-liste non triée pour trouver la valeur minimale.
  • Mémoriser l’indice de cet élément minimal dans une variable nommée PosMin.
  • Échanger l’élément situé à PosMin avec le premier élément de la zone non triée.
  • Avancer la frontière de la zone triée d’une position vers la droite et répéter l’opération jusqu’à ce que le tableau soit entièrement ordonné.

⚠️ Note très importante :

L’utilisation de la fonction prédéfinie en Python .sort() ou sorted() est strictement hors programme dans le cadre des épreuves d’informatique. Vous devez obligatoirement implémenter la logique algorithmique du tri par sélection à l’aide des boucles.

📊 Simulation Visuelle & Algorithme Animé

Visualisez pas à pas l’évolution des indices et l’état de T après chaque passage.

📊 Espace de simulation

450ms
🤖 i
👾 j

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

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

État du tableau T après chaque changement de i :

Étape / i Valeurs du tableau T (éléments permutés en évidence)
Initial –

Algorithme & TDOL :

Procédure Tri_Selection(@T: Tab, n: Entier)
Début
    Pour i de 0 à n-2 Faire
        PosMin ← i
        Pour j de i+1 à n-1 Faire
            Si T[j] < T[PosMin] Alors
                PosMin ← j
            FinSi
        FinPour
        Si PosMin ≠ i Alors
            tmp ← T[i]
            T[i] ← T[PosMin]
            T[PosMin] ← tmp
        FinSi
    FinPour
Fin

TDOL

Objet Type
i, j, PosMin, tmp Entier

💻 Traduction en Python

def tri_selection(T, n):
    for i in range(0, n - 1):
        PosMin = i
        for j in range(i + 1, n):
            if T[j] < T[PosMin]:
                PosMin = j
        if PosMin != i:
            tmp = T[i]
            T[i] = T[PosMin]
            T[PosMin] = tmp

📝 3. Exercice d'application

Situation : Dans un magasin de prêt-à-porter, les prix de plusieurs articles nouvellement reçus sont affichés en vrac sur un écran. Pour aider les clients à trouver les articles du moins cher au plus cher, le gérant souhaite trier automatiquement cette liste de prix en recherchant à chaque fois le prix minimal et en le plaçant en début de rayon (méthode du tri par sélection).

Écrire un programme modulaire permettant de :

  • Saisir le nombre d'articles N (compris entre 2 et 50).
  • Remplir le tableau avec les prix de chaque article.
  • Trier les prix par ordre croissant à l'aide de la procédure du tri par sélection (avec la variable PosMin).
  • Afficher le catalogue des prix triés.

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

Correction détaillée

💻 Programme Principal (Algorithme)

Algorithme Tri_Prix_Magasin
DEBUT
  SaisieTaille(N)
  RemplirTableau(Prix, N)
  TriSelection(Prix, N)
  AfficherTableau(Prix, 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
Prix Tab
N Entier
SaisieTaille Procédure
RemplirTableau Procédure
TriSelection 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 d'articles (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("Prix de l'article ", i+1, " : ")
    Lire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

3. Procédure TriSelection (avec PosMin)

Procedure TriSelection(@t: Tab, n: Entier)
DEBUT
  Pour i de 0 à n-2 Faire
    PosMin ← i
    Pour j de i+1 à n-1 Faire
      Si t[j] < t[PosMin] Alors
        PosMin ← j
      FinSi
    Fin Pour
    Si PosMin ≠ i Alors
      aux ← t[i]
      t[i] ← t[PosMin]
      t[PosMin] ← aux
    FinSi
  Fin Pour
FIN

TDOL : i, j, PosMin, aux (Entiers)

4. Procédure AfficherTableau

Procedure AfficherTableau(t: Tab, n: Entier)
DEBUT
  Ecrire("Catalogue des prix triés par ordre croissant :")
  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 d'articles (2-50) : "))
    while not (2 <= n <= 50):
        n = int(input("Erreur. Nombre d'articles (2-50) : "))
    return n

def remplir_tableau(n):
    return [int(input(f"Prix de l'article {i+1} : ")) for i in range(n)]

def tri_selection(t, n):
    for i in range(n - 1):
        PosMin = i
        for j in range(i + 1, n):
            if t[j] < t[PosMin]:
                PosMin = j
        if PosMin != i:
            t[i], t[PosMin] = t[PosMin], t[i]

def afficher_tableau(t):
    print("Catalogue des prix triés :", t)

# Programme Principal
N = saisie_taille()
Prix = remplir_tableau(N)
tri_selection(Prix, N)
afficher_tableau(Prix)