🐚 Tri par Shell : Cours & Principes

📖 1. Définition

Le tri par Shell (Shell Sort) est une généralisation du tri par insertion. Il permet d’échanger des éléments éloignés en triant d’abord des sous-listes formées par des éléments séparés par un intervalle (pas), puis en réduisant progressivement ce pas jusqu’à 1.

⚙️ 2. Principe de l’algorithme

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

  • Choisir un pas initial (souvent défini par la moitié de la taille du tableau : pas ← n // 2).
  • Appliquer un tri par insertion modifié sur des sous-tableaux espacés de ce pas.
  • Réduire la valeur du pas (pas ← pas // 2) à chaque itération.
  • Répéter l’opération jusqu’à ce que le pas atteigne 0, garantissant un tableau entièrement trié.

⚠️ 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 pas et des insertions espacées.

📊 Simulation Visuelle & Algorithme Animé

Visualisez pas à pas la réduction du pas et les insertions par intervalles.

📊 Espace de simulation

450ms
🤖 pas

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

pas Générez ou lancez la simulation… pas
i – i

État du tableau T après chaque réduction du pas :

Pas Valeurs du tableau T
Initial –

Algorithme & TDOL :

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

TDOL

Objet Type
pas, i, j, val Entier

💻 Traduction en Python

def tri_shell(T, n):
    pas = n // 2
    while pas > 0:
        for i in range(pas, n):
            val = T[i]
            j = i
            while j >= pas and T[j - pas] > val:
                T[j] = T[j - pas]
                j -= pas
            T[j] = val
        pas //= 2

📝 3. Exercice d’application

Situation : Dans un centre de logistique, des colis portant des numéros de série sont alignés sur un tapis roulant. Pour optimiser leur rangement rapide par ordre croissant, le responsable utilise l’algorithme du tri par Shell qui procède par intercalations à intervalles réduits.

Écrire un programme modulaire permettant de :

  • Saisir le nombre de colis N (compris entre 2 et 50).
  • Remplir le tableau avec les numéros de série.
  • Trier les numéros par ordre croissant à l’aide de la procédure du tri par Shell.
  • Afficher le tableau trié.

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

Correction détaillée

💻 Programme Principal (Algorithme)

Algorithme Tri_Colis_Logistique
DEBUT
  SaisieTaille(N)
  RemplirTableau(Colis, N)
  TriShell(Colis, N)
  AfficherTableau(Colis, 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
Colis Tab
N Entier
SaisieTaille Procédure
RemplirTableau Procédure
TriShell 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 colis (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("Colis ", i+1, " : ")
    Lire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

3. Procédure TriShell

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

TDOL : pas, i, j, val (Entiers)

4. Procédure AfficherTableau

Procedure AfficherTableau(t: Tab, n: Entier)
DEBUT
  Ecrire("Colis 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 de colis (2-50) : "))
    while not (2 <= n <= 50):
        n = int(input("Erreur (2-50) : "))
    return n

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

def tri_shell(t, n):
    pas = n // 2
    while pas > 0:
        for i in range(pas, n):
            val = t[i]
            j = i
            while j >= pas and t[j - pas] > val:
                t[j] = t[j - pas]
                j -= pas
            t[j] = val
        pas //= 2

def afficher_tableau(t):
    print("Colis triés par ordre croissant :", t)

# Programme Principal
N = saisie_taille()
Colis = remplir_tableau(N)
tri_shell(Colis, N)
afficher_tableau(Colis)