06b Algorithmes de tri

Table des matières

Créer une liste de données aléatoire
Le tri par sélection
Tri par insertion
Exercices

Introduction : Qu’est-ce que trier ? Pourquoi trier ?
⚓︎

Trier ou effectuer un tri c’est répartir les éléments en paquets correspondant à un certain critère : par exemple séparer les déchets selon leur nature, les personnes d’une assemblée selon leur sexe ou selon leur langue maternelle.

Classer ou effectuer un classement c’est mettre des éléments selon un certain ordre : par exemple ranger les personnes d’une assemblée de la plus petite à la plus grande, ou de la plus jeune à la plus âgée

Dans la vie quotidienne réaliser un tri ou un classement est une opération relativement courante :

classer des factures par date, trier des documents par type (impôts, santé, assurance).
Photos / téléphone : trier par date, par lieu, par personne, par album “vacances / famille”.
Courses / cuisine : trier les aliments (frais / à consommer vite), ranger par catégories (pâtes, conserves, épices).
Cartes / jeux : trier sa main par couleur et par valeur pour jouer plus vite.
Bibliothèque : classer des livres par auteur, thème, ou ordre alphabétique.
Emails : trier par expéditeur, objet, date, importance.
École / travail : classer des élèves par note, trier des candidatures, trier des tâches par priorité.
Transport : trier des itinéraires par durée, coût ou nombre de correspondances.

En informatique les mots tri et trier sont à prendre avec le sens de classement et classer.

1. Créer une liste de données aléatoire
⚓︎

Avant de trier une liste, il faut d'abord en générer une ! Nous allons utiliser le module random pour créer une liste de nombres aléatoires.

Activité n°1 : Générer des données aléatoires

Tester :

🐍 Script Python

import random

def genere_liste_aleatoire(N: int, n: int) -> list:
    """Génère une liste aléatoire de N éléments compris entre 0 et n."""
    return [random.randint(0, n) for _ in range(N)]

# Création d'une liste de 50 valeurs comprises entre 0 et 100
liste_aleatoire = genere_liste_aleatoire(50, 100)
print(liste_aleatoire)

Python

###

Explication

La fonction genere_liste_aleatoire(N, n) crée une liste de N nombres entre 0 et n.
On utilise random.randint(0, n) pour s'assurer que n est inclus dans l’intervalle.
L’utilisation de _ dans la boucle for indique que nous n'avons pas besoin de la valeur de l'index.

2. Le tri par sélection :
⚓︎

Cette méthode de tri s’apparente à celle utilisée pour trier des copies suivant l’ordre décroissant des notes par exemple.

2.1. Le principe
⚓︎

L'idée du tri par sélection est simple :

On cherche le plus petit élément du tableau et on l'échange avec le premier élément.
On cherche ensuite le deuxième plus petit élément et on l'échange avec le deuxième élément.
On continue ainsi jusqu'à ce que toute la liste soit triée.

2.2. Illustration graphique
⚓︎

On cherche le plus grand entier puis on permute. Le plus grand est bien placé. On recommence

Tri par sélection

Nombre de comparaisons :

Calculons la somme

📋 Texte

`S = 15 + 14 + 13 + 12 + … + 4  +  3 +  2  + 1`

Posons une autre somme dans l’autre sens

📋 Texte

`S =   1 +   2  +   3  +  4  +  … + 12 + 13 + 14 + 15`

Faisons la somme membre à membre

📋 Texte

   `2S = 16 + 16 + 16 + 16 +  …  + 16 + 16 + 16 + 16`

Soit

📋 Texte

      2S = 16 x 15
        S = (16 x 15) / 2
        S = 120

2.3. Illustration en vidéo
⚓︎

🎥 Regardez cette vidéo pour mieux comprendre :
https://youtu.be/Ns4TPTC8whw?si=t_V-YDyirqhxmapy

💡 Remarque : Les danseurs s'échangent après chaque comparaison, mais dans le véritable algorithme, l’échange ne se fait qu’une fois par tour.

2.4. Pseudo-code
⚓︎

📋 Texte

ALGORITHME echange (T, i, j)
        tmp <- T[i]                
        T[i] <- T[j]
        T[j] <- tmp

ALGORITHME tri_selection
    N <- longueur(T)
    POUR i ALLANT DE 0 A N-2 FAIRE  
        mini <- i   # Indice du plus petit élément trouvé
        POUR j ALLANT DE i+1 A N-1 FAIRE  
            SI T[j] < T[mini] ALORS  
                mini <- j  
            FIN SI
        FIN POUR
        SI mini ≠ i ALORS  
            ÉCHANGE T[i] AVEC T[mini]  
        FIN SI
    FIN POUR

2.5. Complexité
⚓︎

Analysons le nombre d’opérations effectuées :

La première boucle s’exécute N-1 fois.
La deuxième boucle exécute en moyenne N/2 comparaisons par itération.

➡️ Cela nous donne une complexité de O(N²).

Cela signifie que si on double la taille du tableau, le temps d’exécution est multiplié par 4. Pour N = 10 000, le tri est encore rapide, mais pour N = 1 000 000, il devient lent.

2.6. Stabilité d’un algorithme
⚓︎

Un algorithme de tri est dit stable si l’ordre relatif des éléments identiques est conservé après le tri.

Prenons un exemple concret : imaginons une collection de bouteilles de différentes couleurs et de différents volumes.

Avant le tri, nous avons :

Nous souhaitons trier ces bouteilles par ordre croissant de volume.

Exemple d'un tri non stable : Si l'algorithme n'est pas stable, il peut modifier l’ordre des éléments identiques (bouteilles de même volume). Par exemple, voici un tri incorrect car l’ordre des bouteilles de même volume a changé :

Dans cet exemple :

La bouteille noire de volume 1 est maintenant placée avant la bouteille bleue, alors qu’elle était après initialement.
Les deux bouteilles de volume 4 ont aussi été inversées.

Exemple d'un tri stable :

Un tri stable conserve l’ordre relatif des éléments identiques :

Bouteilles après tri stable

Ici, les bouteilles de même volume restent dans le même ordre qu’au départ.

⚠️ Tri par sélection : non stable (dans sa version classique), car l’échange peut inverser des éléments égaux.

Pourquoi est-ce important ?

L’intérêt d’un tri stable est qu'il permet d'appliquer plusieurs tris successifs sans perdre d’informations. Par exemple, on peut d'abord trier une liste de personnes par âge, puis, dans un second temps, par nom, en gardant les personnes du même âge dans le même ordre qu’avant.

2.7. Preuve de correction
⚓︎

Un algorithme est correct s’il satisfait deux conditions :

1️⃣ Correction partielle : Il fonctionne correctement à chaque étape et atteint son objectif.

2️⃣ Terminaison : Il s’arrête toujours après un nombre fini d’opérations.

2.7.1. Correction partielle
⚓︎

On veut prouver que l’algorithme produit un tableau trié après son exécution.

✅ Invariant de boucle

Avant chaque itération i, les i premiers éléments sont triés et contiennent les i plus petits éléments en ordre croissant.

🧩 Preuve par récurrence

1️⃣ Cas de base (i = 0) :

Avant la première itération, aucun élément n’est trié.
On cherche le plus petit élément et on l’échange avec T[0].
Après cette opération, T[0] est bien le plus petit élément.

2️⃣ Hérédité (i → i+1) :

Supposons que les i premiers éléments sont triés.
À l’itération suivante, on cherche le plus petit élément parmi T[i:n] et on l’échange avec T[i].
Comme T[0:i] était trié, T[0:i+1] reste trié.

3️⃣ Terminaison (i = n-1) :

Il ne reste qu’un seul élément T[n-1], déjà à la bonne place.
Le tableau entier est trié. ✅

✔ Conclusion : L’algorithme produit bien un tableau trié.

2.7.2. Terminaison
⚓︎

On veut prouver que l’algorithme s’arrête toujours.

📌 Analyse de la terminaison

1️⃣ Boucle principale for i in range(n-1)

Elle s’exécute exactement n-1 fois.

2️⃣ Boucle interne for j in range(i+1, n)

Elle compare n-i-1 éléments, donc le nombre de comparaisons diminue progressivement.

✔ Conclusion : L’algorithme termine toujours après n-1 itérations.

2.8. Implémentation en Python
⚓︎

=> CAPYTALE Le code vous sera donné par votre enseignant

Activité n°2 : Générer des données aléatoires

Tester le code suivant :

🐍 Script Python

import random

def genere_liste_aleatoire(N: int, n: int) -> list:
    """Génère une liste aléatoire de N éléments compris entre 0 et n."""
    return [random.randint(0, n) for _ in range(N)]

# Création d'une liste de 20 valeurs comprises entre 0 et 100
liste_aleatoire = genere_liste_aleatoire(20, 100)
print(liste_aleatoire)

Python

###

Activité n°3 : Implémenter le tri par sélection

Tester le code suivant :

🐍 Script Python

def swap(T: list, i: int, j: int) -> None:
    """ Échange les éléments T[i] et T[j] """
    # à compléter

def selection_sort(T: list) -> list:
    """Trie la liste T par sélection"""
    # à compléter

# Tester avec une liste aléatoire
data = genere_liste_aleatoire(5, 20)
print("Liste initiale :", data)
print("Liste triée    :", selection_sort(data))

Explication

swap() est une fonction utilitaire pour échanger deux éléments.
selection_sort() trie la liste en cherchant le plus petit élément à chaque tour.
On affiche la liste avant et après le tri.

Activité n°4 : Tester l'efficacité du tri par sélection

Tester le code suivant :

🐍 Script Python

import time

tailles = [1_000, 2_000, 10_000]

for taille in tailles:
    somme_des_durees = 0
    for _ in range(5):
        liste = genere_liste_aleatoire(taille, 1_000_000)
        start_time = time.perf_counter()
        selection_sort(liste)
        somme_des_durees += time.perf_counter() - start_time
    moyenne = somme_des_durees / 5
    print(f"Temps d'exécution pour {taille}: {moyenne:.6f} secondes")

Explication

On génère des listes aléatoires de 1 000, 2 000 et 10 000 éléments.
On mesure le temps d’exécution moyen du tri sur 5 exécutions.
Remarque : Le temps d’exécution augmente rapidement !

Animation :http://lwh.free.fr/pages/algo/tri/tri_selection.html

3. Tri par insertion
⚓︎

3.1. Le principe
⚓︎

Le tri par insertion est un algorithme de tri stable, souvent utilisé pour de petites listes car il est rapide lorsque l'entrée est presque triée.

🃏 Comparaison avec un jeu de cartes

Le principe du tri par insertion peut être comparé à l'organisation d'un jeu de cartes :

1️⃣ On prend nos cartes mélangées en main.

2️⃣ On sépare nos cartes en deux parties :

📌 Une partie triée (au début, elle ne contient que la première carte).
📌 Une partie non triée (toutes les autres cartes).

3️⃣ À chaque tour, on prend une carte de la partie non triée et on l'insère à sa place dans la partie triée.

4️⃣ On continue jusqu'à ce que toutes les cartes soient triées.

3.2. Illustration graphique
⚓︎

Choisir tri par insertion :

Animation tri par insertion

A chaque étape on insère un nouvel élément dans la partie triée

3.3. Illustration vidéo
⚓︎

💡 Regardez cette vidéo pour mieux comprendre :

📌 Tri par Insertion - Animation

3.4. Pseudo-code
⚓︎

📌 L'algorithme fonctionne en deux étapes :

1️⃣ Chercher la bonne position de l'élément à insérer.

2️⃣ Décaler les autres éléments pour l'insérer.

📋 Texte

ALGORITHME tri_insertion
    PROCEDURE insere(T, i)  
        tmp = T[i]  # Valeur à insérer
        j <- i-1  # Position précédente  

        TANT QUE j >= 0 et T[j] > tmp ALORS  
            T[j+1] <- T [j]  # Décale les éléments  
            j <- j - 1  
        FIN TANT QUE  

        T[j+1] <- tmp  # Insère la valeur  

    PROCEDURE tri_insertion(T)
        n <- longueur(T)  
        POUR i ALLANT DE 1 A n-1 FAIRE  
            insere (T, i)  
        FIN POUR

3.5. Complexité
⚓︎

Le nombre d'itérations dépend de la situation initiale du tableau.

Cas	Nombre d'itérations	Complexité
✅ Meilleur cas (tableau déjà trié)	N	O(N)
❌ Pire cas (tableau trié à l'envers)	N²	O(N²)

📌 Conclusion :

Très efficace pour de petits tableaux ou presque triés.
Moins performant sur de grands tableaux à cause de O(N²).

3.6. Preuve de correction
⚓︎

3.6.1. Correction partielle

⚓︎

On veut prouver que l'algorithme donne un tableau trié à la fin de son exécution.

✅ Invariant de boucle
Avant chaque itération i, le sous-tableau T[0:i] est trié.

🧩 Preuve par récurrence
1️⃣ Cas de base (i = 1) : T[0:1] contient un seul élément → toujours trié. ✅

2️⃣ Hérédité (i → i+1) : T[i] est inséré à la bonne place dans T[0:i], qui est trié → T[0:i+1] reste trié.

3️⃣ Terminaison (i = len(T)) : T[0:len(T)] est entièrement trié.

✔ Conclusion : L'algorithme produit bien un tableau trié à la fin.

3.6.2. Terminaison

⚓︎

L’algorithme ne peut pas boucler indéfiniment et s’arrête toujours.

1️⃣ Boucle for i in range(1, len(T)) : s’exécute len(T) - 1 fois.

2️⃣ Boucle while j >= 0 and T[j] > tmp dans insert : j diminue strictement, donc la boucle while s'arrête forcément.

✔ Conclusion : L’algorithme se termine toujours après au plus O(n²) itérations.

3.7. Implémentation en Python
⚓︎

=> CAPYTALE Le code vous sera donné par votre enseignant

Nous allons maintenant coder le tri par insertion.

Activité n°5 : Création d’une Liste Aléatoire

🔹 Créer une liste aléatoire à trier :

🐍 Script Python

import random
def genere_liste_aleatoire(N, n):
    """Génère une liste aléatoire de N éléments compris entre 0 et n"""
    return [random.randint(0, n) for _ in range(N)]

liste = genere_liste_aleatoire(10, 100)
print("Liste aléatoire :", liste)

Python

###

Activité n°6 : Implémentation du Tri par Insertion

🔹 Compléter le code ci-dessous :

🐍 Script Python

def insert(T, i):
    """Insère la valeur T[i] à la bonne place dans la partie triée."""
    # à compléter

def insertion_sort(T):
    """Tri par insertion."""
    # à compléter

liste_triee = insertion_sort(liste)
print("Liste triée :", liste_triee)

Remarque : on aurait pu également faire une seule fonction

On mesure le temps de tri en fonction de la taille du tableau.

Activité n°7 : Mesurer le Temps d’Exécution

🔹 Tester la rapidité du tri :

🐍 Script Python

import time

tailles = [1_000, 2_000, 10_000]
for taille in tailles:
    somme_des_durees = 0
    for _ in range(5):
        liste = genere_liste_aleatoire(taille, 1_000_000)
        start_time = time.perf_counter()
        insertion_sort(liste)
        somme_des_durees += time.perf_counter() - start_time
    moyenne = somme_des_durees / 5
    print(f"Temps pour {taille} éléments : {moyenne:.4f} secondes")

📌 Remarque :

Un petit tableau sera trié rapidement.
Un grand tableau prendra plus de temps (O(N²)).

Animation : http://lwh.free.fr/pages/algo/tri/tri_insertion.html

4. Exercices
⚓︎

=> CAPYTALE Le code vous sera donné par votre enseignant

Exercice n°1 :

Créer une fonction selection_sort_desc() qui permet trier avec l’algorithme de tri par sélection une liste aléatoire par valeurs décroissantes.

Exercice n°2 :

Créer une fonction selection_sort_asc_partir_fin() qui permet trier avec l’algorithme de tri par sélection une liste aléatoire par valeurs croissantes de manière à compléter l’algorithme suivant :

🐍 Script Python

def selection_sort_asc_partir_fin(T):
    for i in range(…, 0, …):
        maxi = …
        for j in range(…):
            if T[j]> T[…]:
                maxi = j
        if maxi !=i:
            …
    return T

Exercice n°3 :

Créer une fonction selection_sort_desc_partir_fin() qui permet trier avec l’algorithme de tri par sélection et l’algorithme de l’exercice 2, une liste aléatoire par valeurs décroissantes.

06b Algorithmes de tri

Introduction : Qu’est-ce que trier ? Pourquoi trier ? ⚓︎

Introduction : Qu’est-ce que trier ? Pourquoi trier ?

1. Créer une liste de données aléatoire⚓︎

1. Créer une liste de données aléatoire

2. Le tri par sélection :⚓︎

2. Le tri par sélection :

2.1. Le principe⚓︎

2.1. Le principe

2.2. Illustration graphique⚓︎

2.2. Illustration graphique

2.3. Illustration en vidéo⚓︎

2.3. Illustration en vidéo

2.4. Pseudo-code⚓︎

2.4. Pseudo-code

2.5. Complexité⚓︎

2.5. Complexité

2.6. Stabilité d’un algorithme⚓︎

2.6. Stabilité d’un algorithme

2.7. Preuve de correction⚓︎

2.7. Preuve de correction

2.7.1. Correction partielle ⚓︎

2.7.1. Correction partielle

2.7.2. Terminaison⚓︎

2.7.2. Terminaison

2.8. Implémentation en Python⚓︎

2.8. Implémentation en Python

3. Tri par insertion⚓︎

3. Tri par insertion

3.1. Le principe⚓︎

3.1. Le principe

3.2. Illustration graphique⚓︎

3.2. Illustration graphique

3.3. Illustration vidéo⚓︎

3.3. Illustration vidéo

3.4. Pseudo-code⚓︎

3.4. Pseudo-code

3.5. Complexité⚓︎

3.5. Complexité

3.6. Preuve de correction⚓︎

3.6. Preuve de correction

3.6.1. Correction partielle

3.6.2. Terminaison

3.7. Implémentation en Python⚓︎

3.7. Implémentation en Python

4. Exercices⚓︎

4. Exercices

Introduction : Qu’est-ce que trier ? Pourquoi trier ?
⚓︎

1. Créer une liste de données aléatoire
⚓︎

2. Le tri par sélection :
⚓︎

2.1. Le principe
⚓︎

2.2. Illustration graphique
⚓︎

2.3. Illustration en vidéo
⚓︎

2.4. Pseudo-code
⚓︎

2.5. Complexité
⚓︎

2.6. Stabilité d’un algorithme
⚓︎

2.7. Preuve de correction
⚓︎

2.7.1. Correction partielle
⚓︎

2.7.2. Terminaison
⚓︎

2.8. Implémentation en Python
⚓︎

3. Tri par insertion
⚓︎

3.1. Le principe
⚓︎

3.2. Illustration graphique
⚓︎

3.3. Illustration vidéo
⚓︎

3.4. Pseudo-code
⚓︎

3.5. Complexité
⚓︎

3.6. Preuve de correction
⚓︎

3.7. Implémentation en Python
⚓︎

4. Exercices
⚓︎