chapitre 6

Trie interne

Tri des tableaux

 

1-    Introduction :

 

Dans  la majorité des cas la recherche d’un élément donné dans un tableau est difficile et très lente en particulier pour des tableaux très grands.

Pour ce là on utilise la trie à fin de minimisé la recherche (il suffi d’arrivé à une valeur plus grande que la valeur recherche pour s’arrêté).

 

Méthodes de trie :

 

2-  tri par sélection :

 

parcourir tout le tableau affin de recherché la plus petit valeur qui sera ensuite permuté avec la première valeur du tableau.

Cette opération sera répéter jusqu’à se que le tableau sera totalement trié.

 

void tri_select(int tab[],int n)

{          

 

int i,j,Min,Aux ;

for(i=0 ;i<n-1 ;i++)

{

Min=i ;

for(j=i+1 ;j<n ;j++)

if(Tab[j]<Tab[Min])

{

Min=j ;

Aux=Tab[i] ;

Tab[i]=Tab[min] ;

Tab[min]=Aux ;

}

}

}

 

Soit le tableau suivant à trié : n=4

i=0                  1=Min              2                     3

2

1

4

3

        (permutation)

 

i=0 -> min=0,

·         j=i+1=1 et  Tab[j]=1<Tab[Min]=2 donc (on réalise la permutation) :min=j=1, aux=2, tab[i]=tab[2]=1 et tab[min]=tab[1]=2

i=0                  1=Min              2=j                 3

1

2

4

3

       

·        j=j+1(j++)=2  et  Tab[j]=4>Tab[Min]=2

donc on à rien à modifier

·        j=3<n=4  et  Tab[j]=3>Tab[Min]=2

donc on à rien à modifier

·        j=4(>=)4=n -> sort de la boucle.

i=1<n-1=3 -> min=i=1,

·        j=i+1=2 et  Tab[j]=4>Tab[Min]=2

donc rien à modifier 

·        j=j+1(j++)=3  et  Tab[j]=3>Tab[Min]=2

donc on à rien à modifier

·        j=4>=4=n -> sort de la boucle.

i=2<n-1=3 -> min=i=2,

·        j=i+1=3 et  Tab[j]=3<Tab[Min]=4

min=j=3, aux=4, tab[i]= tab[min]= tab[3]=3

tab[min]=4

i=0                  1                      2                     3

1

2

3

4

 

·        j=j+1(j++)=4 (>=) 4 sort de la boucle.

I=3(>=n-1=3) -> fin du programme.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-  trie par insertion :

 

Affin de classé le i éme élément du tableau, on regarde successivement on marche arrière a partir de i-1 .on décale les éléments visité vers la droite pour pouvoir mètre l’élément d’indice i à sa juste place.

 

void tri_inst(int tab[],int n)

{

int i,j,elem ;

for(i=1 ;i<n ;i++)

{

Elem=Tab[i] ;

j=i ;

while(j>0&&Tab[j-1]>Elem)

{

Tab[j]=Tab[j-1] ;

j-- ;

}

}

Tab[j]=Elem ;

}

 

4- trie à bules :

 

è cette méthode est sophistiqué et utiliser dans les cas des grands tableaux (vous pouvez demander par émail ou contacte sur notre site pour avoir cette méthode et la trie insertion plus détaillé avec des exemples).

Dernière mise à jour de cette page le 09/07/2008
Pour me contacté : mahfoudhighaieth2007@yahoo.fr

Créer un site internet gratuit avec E-monsite.com - Signaler un contenu illicite - Voir d'autres sites dans la catégorie Programmation
Comment créer un site - Videos Droles - Clips musique - Cours création de site web