Trois Algorithmes du Tri en C

Soit par exemple un tableau d'entiers de taille N , int T[N] , ce tableau contient des valeurs entiers non triée . Pour le Trier en peut utiliser un de ces 3 algorithmes suivants : ( on suppose qu'on veut trier le tableau par ordre croissant )

ces tris sont générales , ils sont applicables pour des tableaux de n'importe quel type , dans cet article on se limite au tableau d'entier juste pour simplifier .


il faut connaitre qu'il existe 6 types de tri :

• tri par sélection
• tri a bulle
• tri par permutation 
• tri par insertion
• tri par fusion 
• tri rapide

dans cet article on va traiter que les 3 premiers types

Tri par sélection

Cette méthode consiste a trouver le minimum du tableau et le positionner a la première case , une fois cette opération et faite , on la refaire pour le reste du tableau en positionnant le nouveau minimum a la deuxième case etc ...

ce tri ce fait par 2 boucles for de la manière suivante :

int i,j,c;
for(i=0;i<N-1;i++)
    for(j=i+1;j<N;j++)
        if ( T[i] > T[j] ) {
            c = T[i];
            T[i] = T[j];
            T[j] = c;
        }

Tri a bulle

cet algorithme parcourt le tableau en comparant 2 cases successives , lorsqu'il trouve qu'elles ne sont pas dans l'ordre souhaité ( croissant dans ce cas ) , il permute ces 2 cases .
a la fin d'un parcours complet on aura le déplacement du minimum a la fin du tableau .
en faisant cet opération N fois , le tableau serait donc trié .

int i,j,c;

for(j=1;j<=N;j++) // pour faire l'operation N fois
    for(i=0;i<N-1;i++)
        if ( T[i] > T[i+1] ) {
                c = T[i];
                T[i] = T[i+1];
                T[i+1] = c;
        }        

Tri par permutation

cet algorithme consiste a parcourir le tableau jusqu’à ce qu'il trouve un élément inférieur que le précédent ( mal placé ) , il prend cet élément et il le rang a sa place dans le tableau , et il continue le parcours jusqu’à la fin .
et affin de ne pas écraser les valeurs du tableau il faut réaliser une translation des valeurs a l'aide d'une boucle .

int i,j,k,c;

for(i=1;i<N;i++) {

    if ( T[i] < T[i-1] ) { // si l’élément est mal placé

        j = 0;

        while ( T[j] < T[i] ) j++; // cette boucle sort par j = la nouvelle position de l’élément
 
 c = T[i]; // ces 2 lignes servent a translater les cases en avant pour pouvoir insérer l’élément a sa nouvelle position
        for( k = i-1 ; k >= j ; k-- ) T[k+1] = T[k];
 T[j] = c; // l'insertion
    }
}