Ciao,
se vuoi con questo puoi fare il Mergesort su qualsiasi tipo tu voglia (una template function), purché ovviamente siano confrontabili fra loro (cioè esista una regola per il < e <=).
Eccolo:
Codice C++
Codice PHP:
// Merge-Sort Implementation for using with all Type
template<class Typ>
void Merge(vector<Typ>& A, unsigned int i1, unsigned int f1, unsigned int f2)
{
unsigned int i1_ = i1;
// X is an Auxiliary Array of Lenght f2- i1 + 1
vector<Typ> X(f2 - i1 + 1);
unsigned int i = 0;
unsigned int i2 = f1 + 1;
while (i1 <= f1 && i2 <= f2)
{
if (A[i1] <= A[i2])
{
X[i] = A[i1];
++i; ++i1;
}
else
{
X[i] = A[i2];
++i; ++i2;
}
}
if (i1 <= f1)
{
// Copy A[i1; f1] to the End of X
for (unsigned int j = i1; j <= f1; ++j, ++i) X[i] = A[j];
}
else
{
// Copy A[i1; f2] to the End of X
for (unsigned int j = i2; j <= f2; ++j, ++i) X[i] = A[j];
}
// Copy X in A[i1; f2]
for (unsigned int j = 0; j < X.size(); ++j, ++i1_) A[i1_] = X[j];
}
template<class Typ>
void MergeSort(vector<Typ>& A, unsigned int i, unsigned int f)
{
if (i >= f) return;
unsigned int m = (i + f)/2;
MergeSort(A, i, m);
MergeSort(A, m+1, f);
Merge(A, i, m, f);
}
Poi lo usi (nel mio caso dovevo Ordinare "m" Lati secondo la loro lunghezza, ed erano di tipo "edge", una mia classe) normalmente così:
Codice PHP:
MergeSort(Edges, 0, m-1);
Ciao!