Ecole Supérieure d’Economie Numérique
Algorithmique avancée : Les algorithmes de Tri
Dr.Chiheb-Eddine Ben N’Cir
2016 − 2017
Outline
1 Tri à bulles
2 Tri Selection
3 Tri Insertion
4 Tri Fusion
5 Tri Rapide
6 Tri Denombrement
7 Tri par Parquets
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
2 / 23
Algorithme du tri à bulles
Tri à bulles
static void triBulle(int T[]) {
boolean permut;
do {
permut = false;
for (int i = 0; i < T.length - 1; i++) {
if (T[i] > T[i + 1]) {
swap(T, i, i + 1);
permut = true;
}
}
} while (permut);
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
3
3 / 23
Algorithme du Tri Selection
Tri Selection
static void triParSelection(int T[]) {
for (int j = 0; j < T.length - 1; j++) {
int min = j;
for (int i = j + 1; i < T.length; i++) {
if (T[i] < T[min]) {
min = i;
}
}
swap(T, j, min);
}
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
4
4 / 23
Algorithme Tri Insertion
Tri Insertion
public static void triParInsertion(int []T)
{
int cpt;
int element;
for (int i = 1; i < T.length ; i++)
{
element = T[i];
cpt = i - 1;
while(cpt >= 0 & & T[cpt] > element)
{
T[cpt + 1] = T[cpt];
cpt–;
Advertisement
}
T[cpt + 1] = element;
}
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
5
5 / 23
Principe Tri Fusion
Tri Fusion
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
6
6 / 23
Algorithme Tri Fusion
Tri Fusion
public static int[] trifusion(int[] tab)
{
int taille = tab.length;
if(taille<=1)
return tab;
else
{
int mileu = taille/2;
int[] gauche = copie(tab,0,mileu-1);
int[] droite = copie(tab,mileu,taille-1);
return fusion(trifusion(gauche),trifusion(droite));
}
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
7
7 / 23
Suite Tri Fusion
Tri Fusion
public static int[] fusion(int [] tab1, int [] tab2)
{
int tailleg=tab1.length;
int tailled=tab2.length;
int [] res=new int[tailleg + tailled];
int ig=0;
int id=0;
for(int i=0;ig<tailleg & & id<tailled;i++)
if(tab1[ig] <= tab2[id])
res[i]=tab1[ig++];
else
res[i]=tab2[id++];
on copie le reste du tableau de gauche (s’il reste)
while(ig<tailleg) res[i++]=tab1[ig++];
while(id<tailled) / pareil pour le tableau de droite
res[i++]=tab2[id++];
return res;
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
8
8 / 23
Suite Tri Fusion
Tri Fusion
public static int[] copie(int [] tab, int debut, int fin)
{
int[] res=new int[fin-debut+1]; //Pareil, on indique la longueur
for(int i=debut;i<=fin;i++)
{
res[i-debut]=tab[i];
Advertisement
}
return res;
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
9
9 / 23
Principe Tri Rapide
Tri Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
10
10 / 23
Principe Tri Rapide
Tri Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
11
11 / 23
Tri Rapide
Tri Rapide
public static void quicksort(int [] tableau, int début, int fin) {
if (début < fin) {
int indicePivot = partition(tableau, début, fin);
quicksort(tableau, début, indicePivot);
quicksort(tableau, indicePivot+1, fin);
}
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
12
12 / 23
Suite Tri Rapide
Tri Rapide
public static int partition (int [] tableau, int debut, int fin) {
int compteur = debut;
int pivot = tableau[debut];
int i;
for(i=debut+1; i<=fin; i++)
{
if(tableau[i]<pivot) si élément inférieur au pivot
{
compteur++; incrémente compteur cad la place finale du pivot
int temp = tableau[compteur];
tableau[compteur]= tableau[i];
tableau[i] = temp; élément positionné
}
}
int temp = tableau[compteur]; le pivot est placé
tableau[compteur]= tableau[debut];
tableau[debut] = temp;
return compteur;
}
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
13
13 / 23
Donner les etapes du Tri Rapide sur l’exemple suivant
Tri Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
14
14 / 23
Advertisement
Application du Tri Rapide
Tri Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
15
15 / 23
Tri Rapide dans la pratique
Tri Rapide
Le temps d’exécution du tri rapide dépend du caractère équilibré
ou non du partitionnement, qui dépend à son tour des éléments
utilisés pour le partitionnement.
Si le partitionnement est équilibré, l’algorithme s’exécute
asymptotiquement aussi vite que le tri par fusion.
En revanche, si le partitionnement n’est pas équilibré, le tri risque
d’etre aussi lent que le tri par insertion.
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
16
16 / 23
Tri Rapide ou Tri insertion
Tri Rapide
Les banques enregistrent souvent les transactions dans l’ordre
chronologique, mais de nombreuses personnes aiment recevoir
leurs relevés avec les chèques triés par numéros.
En général, les gens signent les chèques dans l’ordre des
numéros et les commerçants les encaissent dans l’ordre d’arrivée.
Le problème consistant à passer d’un ordre chronologique à un
ordre basé sur les numéros de chèque relève donc du problème
du tri de données presque triées.
L’algorithme TRI-INSERTION ou l’algorithme TRI-RAPIDE est plus rapide sur ce
problème ? expliquer
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
17
17 / 23
Tri en temps linéaire: Tri par Denombrement
Tri Denombrement
Le principe du tri par dénombrement est de déterminer, pour chaque élément x
de l’entrée, le nombre d’éléments inférieurs à x.
Cette information peut servir à placer l’élément x directement à sa position dans
le tableau de sortie.
Par exemple, s’il existe 17 éléments inférieurs à x, alors x se trouvera en sortie à
la position 18.
Il faut ajouter aussi la gestion des éléments qui apparaissent plusieurs fois
detail de l’Implementation
On suppose que l’entrée est un tableau A[1..n] et que longueur [A] = n.
Deux autres tableaux : le tableau B[1..n] contient la sortie triée et le tableau
C[0..k] sert d’espace de stockage temporaire.
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
18
18 / 23
Tri par denombrement
Tri Denombrement
TRI-DÉNOMBREMENT(A, B, k)
1 pour i de 0 à k faire
2 C[i] ← 0
3 pour j de 1 à longueur[A] faire
4 C[A[j]] ← C[A[j]] + 1
5 /* C[i] contient maintenant le nombre d’éléments égaux à i.
6 pour i de 1 à k faire
7 C[i] ← C[i] + C[i − 1]
8 /* C[i] contient maintenant le nombre d’éléments inférieurs ou
égaux à i.
9 pour j de longueur[A] jusqu’à 1 faire
Advertisement
10 B[C[A[j]]] ← A[j]
11 C[A[j]] ← C[A[j]] − 1
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
19
19 / 23
Exemple Tri Denombrement
Tri Denombrement
(a) Le tableau A et le tableau auxiliaire C après la ligne 4. (b) Le tableau C après la
ligne 7. (c)-(e) Le tableau en sortie B et le tableau auxiliaire C après une, deux et trois
itérations de la boucle des lignes 9 − 11. Seules les cases en gris clair du tableau B
ont été remplies. (f) Le tableau résultant final B.
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
20
20 / 23
Principe Trie par Paquets
Tri par Parquets
on divise l’intervalle[0, 1) en m sous-intervalles de même taille, ou
paquets, puis on distribue les n nombres de l’entrée dans les
différents paquets.
Comme les entrées sont distribuées de manière uniforme sur
[0, 1), on n’escompte pas qu’un paquet contienne beaucoup de
nombres.
Pour produire le résultat, on se contente de trier les nombres de
chaque paquet, puis de parcourir tous les paquets, dans l’ordre,
en énumérant les éléments de chacun.
Detail de l’implementation
l’entrée est un tableau à n éléments A et que chaque élément A[i] du tableau
satisfait à 0 ≤ A[i] ≤ 1. Le code exige un tableau auxiliaire B[0..n − 1] de listes
chaînées (paquets) et suppose qu’il existe un mécanisme pour la gestion de ce
genre de listes.
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
21
21 / 23
Exemple Tri par paquets
Tri par Parquets
(a) Le tableau en entrée A[1..10]. (b) Le tableau B[0..9] de listes (paquets) triées,
après la ligne 5 de l’algorithme. Le paquet i contient des valeurs appartenant à
l’intervalle semi-ouvert [i/10, (i + 1)/10). Le tableau trié consiste en une
concaténation ordonnée des listes B[0], B[1], ..., B[9].
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
22
22 / 23
Algorithme Tri par paquets
Tri par Parquets
TRI-PAQUETS (A)
1 n ← longueur[A]
2 pour i de 1 à n faire
3 insérer A[i] dans liste B[mA[i]]
4 pour i de 0 à n − 1 faire
5 trier liste B[i] via tri par insertion
6 concaténer les listesB[0], B[1], ..., B[n − 1] dans l’ordre
Chiheb-Eddine Ben N’Cir (ESEN)
les algorithmes de tri
2016
23
23 / 23