Prog-Info > C++ > Tri et Recherche > Tri par sélection.

Le tri par sélection

Le principe est de rechercher la valeur maximale dans un tableau de taille n et de l'échanger avec le dernier élément du tableau. Il faut ensuite faire la même chose avec les n-1 premiers termes du tableau puis les n-2 termes, etc... jusqu'à ce qu'il ne reste plus qu'une seule valeur.

void triSelection(int 
        tableau, int longueur)

        {

           int i, maximum;

           while(longueur>0)

           {

              // recherche 
        de la plus grande valeur du tableau

              maximum = 0;

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

                 if(tableau[i]>tableau[maximum])

                    maximum 
        = i;

              // echange du 
        maximum avec le dernier élément 

              echanger(tableau, 
        maximum, longueur-1);

              // on traite 
        le reste du tableau

              longueur--;

           }

        }

Exemple :
Les différentes étapes de l'algorithme :

7	3	0	1	9	6
7	3	0	1	6	9
6	3	0	1	7	9
1	3	0	6	7	9
1	0	3	6	7	9
0	1	3	6	7	9

Complexité :
Calculons le nombre de passages nécessaire : (n-1)+(n-2)+ ... +2+1 = n*n/2 - n/2.
Le nombre de passages est similaire au tri à bulle.