Ecole Supérieure d’Economie Numérique
Complexité Algorithmique: Les algorithmes de Trie
Dr.Chiheb-Eddine Ben N’Cir
2016 − 2017
Outline
1 Trie à bulles
2 Trie Selection
3 Trie Insertion
4 Trie Fusion
5 Trie Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
2016
2 / 13
Algorithme du trie à bulles
Trie à 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)
Complexité Algorithmique: les algorithmes de trie
2016
3
3 / 13
Algorithme du Trie Selection
Trie Selection
static void triParSelection(int T[]) {
for (int j = 0; j < T.length - 1; j++) {
int min = j;
Publicité
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)
Complexité Algorithmique: les algorithmes de trie
2016
4
4 / 13
Algorithme Trie Insertion
Trie 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–;
}
T[cpt + 1] = element;
}
}
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
2016
5
5 / 13
Principe Trie Fusion
Trie Fusion
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
Publicité
2016
6
6 / 13
Algorithme Trie Fusion
Trie 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)
Complexité Algorithmique: les algorithmes de trie
2016
7
7 / 13
Suite Trie Fusion
Trie 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
Publicité
res[i++]=tab2[id++];
return res;
}
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
2016
8
8 / 13
Suite Trie Fusion
Trie 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];
}
return res;
}
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
2016
9
9 / 13
Principe Trie Rapide
Trie Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
2016
10
10 / 13
Principe Trie Rapide
Trie Rapide
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de trie
2016
11
11 / 13
Trie Rapide
Trie Rapide
Publicité
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)
Complexité Algorithmique: les algorithmes de trie
2016
12
12 / 13
Suite Trie Rapide
Trie 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)
Complexité Algorithmique: les algorithmes de trie
2016
13
13 / 13