Prog-Info > C++ > Tri et Recherche > Tri par création.

Le tri par création

Cet algorithme est un peu compliqué et ne fournit pas de résultats exceptionnels. Il peut être utilisé quand on veut garder une copie de l'original. Cependant on pourrait très bien en faire une copie juste avant.
Le principe est de créer un nouveau tableau de la même taille et vide. Puis, on recherche la plus petite valeur du tableau et on la place au tout début du nouveau tableau. On place à la suite les valeurs qui suivent la plus petite valeur.

int positionSuivant(int 
    *tableau, const int longueur, int 
    positionDernier, int maximum)

        {

           int i;

           int positionDernier = tableau[positionDernier];

           int positionSuivant = -1;

           int valeurSuivant = maximum;

        

           // recherche de la valeur suivante 
        à travers le tableau

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

           {

              if((tableau[i]==valeurDernier) 
        && (i>positionDernier))

                 return 
        i; // valeur suivante = valeur dernier élément

              if((tableau[i]>valeurDernier) 
        && (tableau[i]<valeurSuivant))

              { // on a trouvé 
        une valeur qui pourrait être la suivante

                 valeurSuivant = 
        tableau[i];

                 positionSuivant 
        = i;

              }

              if((tableau[i]==maximum) 
        && (positionSuivant==-1))

                 // 
        le plus grand élément du tableau a été trouvé

                 // si pas d'élt 
        suivant, position élt suivant = position dern élt

                 positionSuivant 
        = i;

           }

           return positionSuivant;

        }


		
        void triParCreation(int 
        *tableauSource, int *tableauDestination, 
        const int                     longueur)

        {

           int i;

           int positionDernier = 0;

           int minimum = tableauSource[0];

           int maximum = tableauSource[0];

        

           // recherche du plus petit et 
        plus grand élément du tableau

           // recherche de la position du plus petit élément

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

           {

              if(tableauSource[i]<minimum)

              {

                 positionDernier=i;

                 minimum = tableauSource[i];

              }

              else if(tableauSource[i]>maximum)

                 maximum = tableauSource[i];

           }

           // placement du premier élément 
        du tableau destination 

           tableauDestination[0] = minimum;

        

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

           { //recherche de la position de 
        l'élément suivant

              positionDernier = positionSuivant(tableauSource, 
        longueur,                                         positionDernier, 
        maximum); 

              if(positionDernier!=-1) 
        // si élément suivant trouvé

                 // 
        placement de l'élément dans le tableau destination

                 tableauDestination[i] 
        = tableauSource[positionDernier];

              else 
        // position de l'élément suivant non 
        trouvée

                 printf("Erreur, 
        élément perdu");

           }

        }

Exemple :
Les grandes étapes de l'algorithme :

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

Complexité :
Le nombre de comparaisons effectuées dans cet algorithme est à peu près fixe. Il est de l'ordre de n*n plus quelques autres opérations.