Les algorithmes de tris
Tri par comparaison
CPGE Moulay Youssef
Rabat
MPSI
2024 / 2025
0 / 12
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Plan
1 Introduction
2 Tri à bulles
3 Tri par sélection
4 Tri par insertion
5 Tri par dénombrement
1 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Introduction
Nous avons vu la structure de données des listes, qui peut contenir plusieurs valeurs,
éventuellement de types différents.
Parmi les traitement qu’on peut faire sur un ensemble de données est de les trier
selon un ordre prédéfini.
On s’intéresse dans ce cours de trier un ensemble de données ( en général listes de
nombres réels).
Quels sont les types de tri qui existent ? Quelles différences entre eux ?
Quelles sont les applications principales des méthodes de tris ?
2 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Problème de tri
Souvent, on s’intéresse aux algorithmes de tris qui procèdent par comparaison entre les
éléments d’un tableau (on peut voir d’autres).
Le problème est donc de prendre en entrée un tableau t = [a0 , a1 , .., an−1 ] d’éléments d’un
ensemble E muni d’une relation d’ordre ≤. Et de donner en sortie le même tableau trié.
Remarque :
Les méthodes de tris peuvent aussi différer suivant que la structure de donnée à trier
soit mutable ou pas : dans le cas d’une structure mutable, on cherchera à trier les
éléments en place, c’est à dire sans coût spatial supplémentaire.
Il existe des algorithmes qui n’utilisent pas de comparaison entre les éléments, mais
se base sur une information supplémentaire dont on dispose sur les éléments à trier
(ex : Tri par base, Tri par comptage, ..).
On dit qu’un algorithme de tri est stable lorsqu’il préserve l’ordre des indices entre
deux éléments équivalents.
3 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri à bulles
Le tri à bulles est parmi les méthodes de tri les plus naïves et simples, son principe est de
comparer chaque deux valeurs adjacentes et d’inverser leurs positions si elles sont mal
placées.
Exemple :
4 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
La technique est de faire remonter (ou descendre) les plus petit éléments en tête du
tableau (comme des bulles).
Voici une version du tri à bulles.
Exercice :
1 Donner le nombre de comparaisons nécessaires pour cet algorithme.
2 Implémenter le Tri à bulles en Python.
5 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par sélection
Le principe de ce tri est de rechercher le plus grand élément(ou le plus petit), le placer en
fin de tableau (ou en début), recommencer avec le second plus grand (ou le second plus
petit), le placer en avant dernière position (ou en seconde position) et ainsi de suite
jusqu’à avoir parcouru la totalité du tableau.
6 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par sélection
Exemple :
Exercice :
1 Donner le nombre de comparaisons nécessaires pour cet algorithme.
2 Implémenter le Tri par sélection en Python.
7 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par insertion
C’est le tri souvent utilisé naturellement pour trier des cartes à jouer : l’objectif d’une
étape est d’insérer le i-ème élément à sa place parmi ceux qui précèdent. Il faut pour cela
trouver où l’élément doit être inséré en le comparant aux autres, puis décaler les éléments
afin de pouvoir l’insérer.
8 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par insertion
Exemple :
Exercice :
1 Donner le nombre de comparaisons nécessaires pour cet algorithme.
2 Implémenter le Tri par insertion en Python. 9 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par dénombrement
Dans les trois algorithmes de tri vus précédemment, la technique principale est toujours
de comparer les éléments du tableau plusieurs fois jusqu’à avoir le tableau trié. Ces
algorithmes resteront valables pour n’importe quel données numériques (On a pas
forcément une information sur les valeurs des données du tableau).
Il existent d’autres méthodes de tri qui utilisent des informations préalables sur les
valeurs des éléments du tableau.
Par exemple, l’algorithme de tri par dénombrement - ou par comptage - (counting sort).
Cet algorithme est applicable lorsque les éléments à trier ne peuvent prendre qu’un
nombre fini de valeurs dans un intervalle connue au départ.
10 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par dénombrement
Le principe est le suivant :
Considérons le cas d’un tableau t de longueur n dont les valeurs sont prises dans
l’intervalle entier [|0, k − 1|].
En un parcours du tableau t il est possible de dénombrer le nombre d’apparitions de
chacune des k valeurs possibles.
Chaque valeur de l’intervalle [|0, k − 1|] est ensuite rangée dans le tableau t autant de
fois que nécessaire.
Cette technique de tri est Applicable quand :
Les éléments à trier ne peuvent prendre qu’un nombre fini de valeurs.
La différence k entre la valeur maximale et la valeur minimale est proche du nombre n
des valeur à trier.
11 / 12
Les algorithmes de tris
Introduction Tri à bulles Tri par sélection Tri par insertion Tri par dénombrement
Tri par dénombrement
Exemple :
Trier la liste : A = [5, 1, 3, 4, 3, 1, 4, 5, 0, 1]
Les nombres appartiennent à l’intervalle [0, 5]. On crée un tableau T contenant 6
nombres :
T = [0, 0, 0, 0, 0, 0]
On parcoure la liste A en mettant dans T [i] le nombre d’occurrences de i pour i ∈ [0, 5]
T = [1, 3, 0, 2, 2, 2]
Pour i dans [0, 5], On affiche chaque i , T [i] fois.
[0, 1, 1, 1, 3, 3, 4, 4, 5, 5]
Exercice :
1 Donner le nombre de comparaisons nécessaires pour cet algorithme.
2 Implémenter le Tri par dénombrement en Python.
12 / 12
Les algorithmes de tris
