Merge sort

Commenter

Contenu du snippet

Ce code est un Merge Sort. Il permet de trier un tableau par séparations successives. Son intérêt est sa rapidité. Pour plus d'infos voyez sur google ou wikipédia c'est très bien expliqué.

Source / Exemple : 


template <class T> void MergeSort(T *t, signed long int beg, signed long int end)
{
 //Si la section est de 1 ou 2 champs ==> check si en ordre et fin du tri
   if ((end - beg) < 2)
   { 
    if (t[beg] > t[end])
    {     
     T temp = t[end];
     t[end] = t[beg];
     t[beg] = temp;
    }
   } 
 //Fin section d'un ou 2 champs
 
 //> 2 champs ==> lance le tri (effet de récurrence) et rassemble
   else
   {
    //Définition des nouvelles valeurs de début et de fin
      signed long int newend = (beg + end) >> 1;
      signed long int newbeg = newend + 1;
    //Fin Définition des nouvelles valeurs de début et de fin
    MergeSort(t, beg, newend);
    MergeSort(t, newbeg, end);
    
    //Rassemblement des section séparée et tri
      ++newend;
      ++end;
      
      for (signed long int i = beg; i < newend; ++i)
       for (signed long int j = newbeg; j < end; ++j)
       {
        if (t[i] <= t[j])
         break;
         
        //Décalage 
          T temp = t[j];        
        
          for (signed long int k = j; k > i; --k)
           t[k] = t[k - 1];           
          t[i] = temp;
          
          ++i;      //Vu le décalage, l'indice de la nouvelle valeur est à augmenter
          ++newend; //Vu le décalage, la fin du premier est plus loin
          ++newbeg; //Vu le décalage, le début du deuxième est plus loin
        //Fin Décalage     
       } 
    //Fin Rassemblement des section séparée et tri
   } 
 //Fin > 2 champs
} 
//-------------------------------------------------------------------------------------------------

int main()
{
 srand(clock());
 int n;
 cout << "Entrer la taille du tableau initial : "; cin >> n;
 cout << "\n";

 int *t = new int[n]; 
 for(int i = 0; i < n; i++)
 {
  t[i] = (rand()%50)-10;
  cout << t[i] << ' ';
 } 
 cout << endl;

 MergeSort(t, 0, n - 1);
 
 for(int i = 0; i < n; i++)
  cout << t[i] << ' ';

 delete t; 
 return 0;
}

Conclusion :


Cet algo est une fonction récursive. Pour plus d'infos voyez le zip.
La partie de rassemblement de 2 morceaux peut être accélérée. J'y travaille actuellement.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_dominion)