Cours

📚 Algorithmes sur les Tableaux
Optimisation du Tri : Algorithmes de Comparaison

🎯 Définitions et Problématiques

📖 Qu'est-ce que trier ?
Trier consiste à organiser un ensemble d'éléments dans un ordre précis (généralement croissant ou décroissant). C'est une opération fondamentale en informatique, utilisée dans de nombreux domaines.
📊
Classement de Données
Organisation et structuration des informations pour faciliter leur consultation et leur analyse.
⚙️
Préparation Algorithmique
Préparation de données pour d'autres algorithmes qui nécessitent des données ordonnées.
🚀
Optimisation des Performances
Amélioration significative des performances de recherche et d'accès aux données.
🔧 Stratégies de Tri
On peut trier des données de plusieurs manières :
  • Par comparaison : on compare les éléments entre eux
  • Sans comparaison : on utilise des propriétés spécifiques des données

🔍 Tri par Sélection

📖 Principe de Fonctionnement
Au début de l'algorithme, on cherche la plus petite valeur de la liste et on l'échange avec la valeur située à la première position. À partir de cette itération, on considère que la liste à trier est composée d'une partie triée et d'une partie non triée.
1. Chercher la valeur la plus petite de la zone non triée
2. Placer cette valeur au début de la zone non triée
3. Étendre la zone triée d'un élément
4. Répéter jusqu'à ce que toute la liste soit triée
💡 Exemple Illustratif
Liste initiale : [5, 2, 4, 6, 1, 3]
Étapes Liste en cours Min sélectionné
Début [5, 2, 4, 6, 1, 3] 1
Étape 1 [1, 2, 4, 6, 5, 3] 2
Étape 2 [1, 2, 3, 6, 5, 4] 3
... ... ...
Final [1, 2, 3, 4, 5, 6] -
🐍 Implémentation en Python
On va avoir besoin de trois fonctions :
  • indice_minimum_tranche : trouve l'indice du minimum dans une portion de la liste
  • echange_valeur : échange deux valeurs dans la liste
  • tri_selection : réalise le tri complet
🦊 Exercice Important : Indice de la valeur minimum dans une tranche
Écrire une fonction indice_minimum_tranche qui prend en paramètres une liste, un indice de début et qui renvoie l'indice de la valeur la plus petite dans la tranche donnée.

Attention, cette fonction doit bien vérifier que les indices soient bien compris dans la liste pour éviter les erreurs de Out Of Range.
💡 Exemple
>>> liste = [1,5,2,4,0,8]
>>> indice_minimum_tranche(liste,1)
4
🦊 Exercice Important : Échange de valeur à l'aide des indices
Écrire une fonction echange_valeur qui prend en paramètre une liste et deux indices et échange les positions des deux valeurs dans la liste

Attention, cette fonction fait une modification par effet de bord et ne renvoie rien.
💡 Exemple
>>> liste = [1,5,2,4,0,8]
>>> echange_valeur(liste, 0, 4)
>>> print(liste)
[0,5,2,4,1,8]
🦊 Exercice Important : Tri par sélection du minimum
Écrire une fonction tri_selection_minimum qui prend en paramètre une liste et renvoie sa permutation triée.

Attention, on ne doit pas modifier la liste passée en paramètre car cela pourrait la changer dans toute la suite du programme et il peut y avoir des cas d'usage où cette liste ne doit pas être modifiée.
💡 Exemple
>>> liste = [1,5,2,4,0,8]
>>> print(tri_selection_minimum(liste))
[0,1,2,4,5,8]

🔄 Tri par Insertion

📖 Principe de Fonctionnement
On considère que la liste à trier est composée d'une partie triée composée d'un élément et une partie non triée. À chaque itération i du tri, on va chercher à déplacer la valeur que l'on retrouve à la position i à sa bonne position dans la zone triée.
1. Considérer le premier élément comme déjà trié
2. Prendre l'élément suivant de la zone non triée
3. L'insérer à sa place dans la zone triée
4. Répéter jusqu'à ce que toute la liste soit triée
💡 Exemple Illustratif
Liste initiale : [5, 2, 4, 6, 1, 3]
Étapes Liste en cours Élément inséré
Début [5, 2, 4, 6, 1, 3] -
Étape 1 [2, 5, 4, 6, 1, 3] 2
Étape 2 [2, 4, 5, 6, 1, 3] 4
Étape 3 [2, 4, 5, 6, 1, 3] 6
Étape 4 [1, 2, 4, 5, 6, 3] 1
Étape 5 [1, 2, 3, 4, 5, 6] 3
Final [1, 2, 3, 4, 5, 6] -
🐍 Implémentation en Python
On va avoir besoin de trois fonctions :
  • echange_valeur : échange deux valeurs dans la liste
  • insertion_zone_triee : insère un élément à sa place dans la zone triée
  • tri_insertion : réalise le tri complet
🦊 Exercice Important : Échange de valeur à l'aide des indices
Écrire une fonction echange_valeur qui prend en paramètre une liste et deux indices et échange les positions des deux valeurs dans la liste

Attention, cette fonction fait une modification par effet de bord et ne renvoie rien.
💡 Exemple
>>> liste = [1,5,2,4,0,8]
>>> echange_valeur(liste, 0, 4)
>>> print(liste)
[0,5,2,4,1,8]
🦊 Exercice Important : Insertion d'une valeur dans une zone triée
Écrire une fonction insertion_zone_triee qui prend en paramètre une liste, et un indice correspondant à celui de la valeur qui est juste après la zone triée. Cette fonction échange la valeur à l'indice avec celles qui sont avant elles pour trouver sa bonne place.

Attention, cette fonction doit bien vérifier que les indices soient bien compris dans la liste pour éviter les erreurs de Out Of Range.
💡 Exemple
>>> liste = [1,5,2,4,0,8]
>>> insertion_zone_triee(liste,2)
>>> print(liste)
[1,2,5,4,0,8]
🦊 Exercice Important : Tri par insertion
Écrire une fonction tri_insertion qui prend en paramètre une liste et renvoie sa permutation triée.

Attention, on ne doit pas modifier la liste passée en paramètre car cela pourrait la changer dans toute la suite du programme et il peut y avoir des cas d'usage où cette liste ne doit pas être modifiée.
💡 Exemple
>>> liste = [1,5,2,4,0,8]
>>> print(tri_insertion(liste))
[0,1,2,4,5,8]

🔢 Tris Sans Comparaison

📖 Définition
Les tris sans comparaison sont des algorithmes qui n'utilisent pas de comparaisons entre éléments mais exploitent des propriétés spécifiques des données pour les organiser.
🧮 Tri par Dénombrement
Le tri par dénombrement est un algorithme de tri qui n'agit pas par comparaisons mais par comptage des éléments de la liste.

Exemple : Dans la liste L [3,2,1,2], on peut dénombrer les valeurs de cette manière : une occurence de 1, deux occurences de 2 et une occurence de 3.
1. Créer une liste d'occurrences de taille max+1
2. Compter les occurrences de chaque élément
3. Reconstruire la liste triée à partir des compteurs
⚙️ Principe de fonctionnement
On considère la liste L précédente :
  • On crée une liste d'occurrences contenant un nombre de 0 équivalent à la valeur maximale + 1 de la liste à trier
  • On parcourt la liste L à trier et à chaque élément, on incrémente la valeur à l'indice du nombre rencontré
  • On reconstruit la liste triée en parcourant la liste d'occurrences
Phase 1 : Comptage des occurrences
Itération L Occurrences
0 [3,2,1,2] [0, 0, 0, 0]
1 [3, 2, 1, 2] [0, 0, 0, 1]
2 [3, 2, 1, 2] [0, 0, 1, 1]
3 [3, 2, 1, 2] [0, 1, 1, 1]
4 [3, 2, 1, 2] [0, 1, 2, 1]
Phase 2 : Reconstruction de la liste triée
Itération Occurrences Liste triée
1 [0, 1, 2, 1] []
2 [0, 1, 2, 1] [1]
3 [0, 1, 2, 1] [1, 2, 2]
4 [0, 1, 2, 1] [1,2,2,3]