Salve, devo comparare gli algoritmi di ordinamento Shellsort e Mergesort.
A livello di codice il Mergesort è più complesso ed infatti calcolando i tempi di esecuzione dei due su diversi array mi viene un tempo di esecuzione del Mergesort mediamente 4 volte superiore al tempo di esecuzione dello Shellsort. Osservando il cosiddetto "worst-case time complexity" tuttavia osservo come quello del Mergesort ( n * ln(n) )sia molto inferiore rispetto a quello dello Shellsort ( n^2 ). Mi chiedevo dunque quali sono le conclusioni che dovrei concludere sul confronto tra questi due metodi di ordinamento.
Per scrupolo ho allegato il codice che ho scritto su Java.
// ALGORITMO DI ORDINAMENTO PER FUSIONE
void fondi (int[] a, int sinistra, int centro, int destra) {
int[] b = new int [destra-sinistra+1] ;
int i = sinistra ;
int j = centro + 1 ;
int k = 0 ;
while ( (i <= centro) && (j <= destra) ) {
if (a[i] < a[j]) {
b[k] = a[i] ;
i += 1 ;
k += 1 ;
} else {
b[k] = a[j] ;
j += 1 ;
k += 1 ;
}
}
while (i <= centro) {
b[k] = a[i] ;
i += 1 ;
k += 1 ;
}
while (j <= destra) {
b[k] = a[j] ;
j += 1 ;
k += 1 ;
}
for (i = sinistra; i <= destra; i++) {
a[i] = b[i-sinistra] ;
}
}
void ordina (int[] a, int sinistra, int destra) {
if (sinistra < destra) {
int centro = (sinistra + destra) / 2 ;
ordina (a, sinistra, centro) ;
ordina (a, centro + 1, destra) ;
fondi (a, sinistra, centro, destra) ;
}
}
// Tempo di esecuzione
long timeMergeSort (int[] a) {
long start = System.nanoTime() ;
ordina (a, 0, a.length - 1) ;
long end = System.nanoTime() ;
return end - start ;
}
long meanTimeMergeSort (int[] a) {
long m = 0 ;
for (int i = 1; i <= 100000; i++) {
m += timeMergeSort(a) ;
}
return m / 100000 ;
}
// Tempo di esecuzione Shellsort
long timeShellsort (int[] a) {
long start = System.nanoTime() ;
int n = a.length ;
int k = 1 ;
int gap = 1 ;
int temp = 0 ;
int j = 0 ;
while (gap > 0) {
gap = (int) n / Math.pow(2,k) ;
for (int i = gap; i < n; i++) {
temp = a[i] ;
for (j = i; j >= gap && a[j-gap] > temp; j = j-gap) {
a[j] = a[j-gap] ;
}
a[j] = temp ;
}
k += 1 ;
}
long end = System.nanoTime() ;
return end - start ;
}
long meanTimeShellsort (int[] a) {
long m = 0 ;
for (int i = 1; i <= 100000; i++) {
m += timeShellsort(a) ;
}
return m / 100000 ;
}