ALGORITHMES DE TRI PAR COMPARAISON

1
 CATEGORIES DES ALGORTIHMES DE TRI

1- Tri par comparaison: dans cette catégorie, les éléments à trier sont
comparés deux à deux, en utilisant des opérations de comparaison pour
déterminer leur ordre relatif.
Les algorithmes les plus courants de cette catégorie sont:
Tri par sélection (selection sort);
Tri par insertion (insertion sort);
Tri à bulles (bubble sort);
Tri par tas (heap sort);
Tri de Shell (shell sort)

2
 CATEGORIES DES ALGORTIHMES DE TRI

2- Diviser pour régner: c’est une stratégie de résolution de problèmes qui

consiste à diviser un problème en sous-problèmes plus petits, les résoudre
séparément, puis combiner les résultats pour résoudre le problème initial.
Les algorithmes les plus courants de cette catégorie sont:

Tri rapide (quick sort);

Tri par fusion (merge sort);

3
 CATEGORIES DES ALGORTIHMES DE TRI

3- Tri par comptage: le tri par comptage est une méthode de tri qui compte
le nombre d’occurrences de chaque élément dans une liste et les organise
dans l’ordre croissant ou décroissant.
Les algorithmes les plus courants de cette catégorie sont:

Tri par comptage (counting sort);

Tri par base (radix sort)

4
TRI PAR SELECTION

5
 TRI PAR SELECTION

Principe:
• Le principe du tri par sélection consiste, à chaque étape, à retrouver le
plus petit élément non encore trié et à le placer après les éléments déjà
triés. Il fonctionne comme suit:
Trouver le plus petit élément du tableau et l’échanger avec le
premier élément;
Trouver le deuxième plus petit élément et l’échanger avec le
deuxième élément du tableau;
Répéter le processus de recherche du plus petit élément suivant et
le placer dans la position correcte jusqu’à ce qu’un tableau soit trié.

6
 TRI PAR SELECTION (EXEMPLE)

8 12 3 16 18 2 5 20 6

0 1 2 3 4 5 6 7 8

2 3 5 6 8 12 16 18 20

0 1 2 3 4 5 6 7 8
7
 TRI PAR SELECTION-
IMPLEMENTATION

9
 TRI PAR SELECTION-RECAPITULATIF

1.Sélectionner l'élément minimum : L'algorithme commence par

parcourir tout le tableau à trier pour trouver l'élément minimum.
2.Échanger : Une fois que l'élément minimum est trouvé, il est échangé
avec l'élément situé à la première position du tableau (ou à la position
actuelle de la boucle si nous avançons progressivement dans le tableau).
3.Répéter : Ensuite, l'algorithme parcourt le reste du tableau (à partir de
la position suivante à celle de l'élément précédemment sélectionné) pour
trouver le prochain élément minimum. Ce processus se répète jusqu'à ce
que tous les éléments soient triés.

10
 TRI PAR SELECTION-COMPLEXITE

La complexité de l’algorithme de tri par sélection est

O(n²)
une complexité quadratique

11
 TRI PAR SELECTION-EXERCICE

Ecrire un programme en C qui trie dans l’ordre décroissant un tableau de 6 entiers en

utilisant l’algorithme de tri par sélection.

12
 TRI PAR SELECTION-SOLUTION
DE L’EXERCICE

13
TRI PAR INSERTION

14
 TRI PAR INSERTION

1.Insertion séquentielle : L'algorithme commence par considérer un

élément du tableau à trier à la fois. Au début, le premier élément du
tableau est considéré comme étant trié (puisqu'il n'y a qu'un seul élément).
2.Insertion dans la bonne position : Pour chaque nouvel élément
considéré, l'algorithme le compare à tous les éléments précédents déjà
triés. Il le place à sa position correcte dans la partie déjà triée du tableau en
déplaçant les éléments plus grands (ou plus petits selon l'ordre de tri) vers
la droite pour faire de la place.
3.Répéter : Ce processus se répète pour chaque élément du tableau,
jusqu'à ce que tous les éléments soient correctement placés.

15
 TRI PAR INSERTION-PRINCIPE

• Le tri par insertion est souvent comparé à la manière dont on trie des
cartes en main, en prenant une carte à la fois et en l'insérant à sa place
correcte parmi les cartes déjà triées.
• Cet algorithme a une complexité quadratique dans le pire des cas (O(n^2)),
mais il est efficace pour les petites quantités de données ou pour les
tableaux qui sont déjà presque triés, car son temps d'exécution dépend en
partie de l'ordre initial des éléments.

16
 TRI PAR INSERTION-
IMPLEMENTATION

17
TRI PAR BULLES

18
 TRI PAR BULLES

• Le tri à bulles est un algorithme de tri simple et intuitif qui fonctionne en parcourant
répétitivement le tableau à trier, en comparant chaque élément adjacent et en les échangeant
s'ils ne sont pas dans le bon ordre. Ce processus est répété jusqu'à ce que le tableau soit
entièrement trié.
Voici le principe du tri à bulles :
1.Comparaison : L'algorithme commence par comparer les éléments adjacents du tableau,
en commençant par les premiers éléments. Il compare chaque élément avec son voisin de
droite.
2.Échange : Si un élément est plus grand que son voisin de droite (dans le cas d'un tri
croissant), les deux éléments sont échangés. Ainsi, les éléments plus grands "sont poussés
vers le haut" (ou vers la fin du tableau).
3.Répétition : Ce processus est répété pour chaque paire d'éléments dans le tableau, de sorte
que les éléments plus grands continuent à "remonter" vers le haut du tableau à chaque
itération.
4.Itérations : Ces comparaisons et échanges sont répétés jusqu'à ce qu'il n'y ait plus
19
d'échanges à effectuer, ce qui signifie que le tableau est maintenant trié.
 TRI PAR BULLES

Dans le tri par bulle, nous échangeons deux éléments successifs T[i-1] et T[i] s’ils ne sont
pas dans l’ordre. Évidemment, il faut faire cela un grand nombre de fois pour obtenir un
tableau trié. Plus précisément, nous faisons remonter le maximum à sa place définitive
par échanges successifs avec ses voisins.

20
 TRI PAR BULLES-
IMPLEMENTATION

21