Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 88:
a[k] ← b[k - left]
Una implementazione in C++:
<source lang="cpp">
#include <iostream>
using namespace std;
void merge(int *ar1, int *aux, int lo, int mid, int hi)
{
// Copy on aux just what we need, this is necessary since we can't iterate through array and set its elements while
// they are being exchanged and read at the same time
memcpy(&aux[lo], &ar1[lo], (hi+1-lo)*sizeof(int));
int l1 = lo;
int l2 = mid+1;
int i = lo;
while(l1 <= mid && l2 <= hi)
{
if(aux[l1] <= aux[l2])
{
ar1[i] = aux[l1];
l1++;
}
else
{
ar1[i] = aux[l2];
l2++;
}
i++;
}
if(l1 > mid)
{
memcpy(&ar1[i], &aux[l2], (hi+1-l2)*sizeof(int));
}
else
{
memcpy(&ar1[i], &aux[l1], (mid+1-l1)*sizeof(int));
}
}
void mergesort(int *array, int *aux, int lo, int hi)
{
if(lo >= hi)
return;
int hi1 = (hi-lo)/2;
mergesort(array, aux, lo, lo+hi1);
mergesort(array, aux, lo+hi1+1, hi);
merge(array,aux,lo,lo+hi1,hi);
}
int main (int argc, char **argv)
{
int array[] = {10,9,8,7,6,5,4,3,2,1};
const int sz = sizeof(array) / sizeof(int);
int aux[sz]; // Auxiliary buffer
mergesort(array,aux,0,sz-1);
for(int i=0; i<sz; i++)
cout << array[i] << " ";
}
</source>
== Analisi ==
L'algoritmo Merge Sort, per ordinare una sequenza di <math>n</math> oggetti, ha complessità temporale <math>T(n) = \Theta(n\log n)</math> sia nel caso medio che nel caso pessimo. Infatti:
| |||