sic2
01-12-2011, 00:48
Ciao a tutti!
sto analizzando l'algoritmo di Merge Sort a fondo e dopo aver ottenuto il grafico n*log(n) che conferma la regola, voglio vedere come l'algoritmo spende il "proprio tempo" nella fase di merging.
In teoria la fase di merging dovrebbe essere più rapida quando si "uniscono" due array di piccole dimensioni, e poi dovrebbe aumentare quando si risale l'albero, giusto???
Questo è il codice che ho usato per raccogliere i dati:
leftArray = MergeSort(leftArray);
rightArray = MergeSort(rightArray);
long time = System.nanoTime();
int[] mergedArray = merge(leftArray, rightArray);
dataCollection[indexDataCollection] = dataCollection[indexDataCollection] + System.nanoTime() - time;
indexDataCollection++;
return mergedArray;
In allegato trovate il grafico che ho ottenuto.
Tuttavia non riesco a giustificare la distribuzione dei punti nel grafico.
L'asse delle x indica lo stage del merge sort. Quindi a x = 0 l'array è completamente disordinato, mentre a x = 5000 è ordinato.
L'asse delle y indica il tempo impiegato allo stage x(i).
sto analizzando l'algoritmo di Merge Sort a fondo e dopo aver ottenuto il grafico n*log(n) che conferma la regola, voglio vedere come l'algoritmo spende il "proprio tempo" nella fase di merging.
In teoria la fase di merging dovrebbe essere più rapida quando si "uniscono" due array di piccole dimensioni, e poi dovrebbe aumentare quando si risale l'albero, giusto???
Questo è il codice che ho usato per raccogliere i dati:
leftArray = MergeSort(leftArray);
rightArray = MergeSort(rightArray);
long time = System.nanoTime();
int[] mergedArray = merge(leftArray, rightArray);
dataCollection[indexDataCollection] = dataCollection[indexDataCollection] + System.nanoTime() - time;
indexDataCollection++;
return mergedArray;
In allegato trovate il grafico che ho ottenuto.
Tuttavia non riesco a giustificare la distribuzione dei punti nel grafico.
L'asse delle x indica lo stage del merge sort. Quindi a x = 0 l'array è completamente disordinato, mentre a x = 5000 è ordinato.
L'asse delle y indica il tempo impiegato allo stage x(i).