- 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;
- }
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;
}