Complexité Algorithmique: Les algorithmes de Trie

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

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

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

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