Shellsort VS Mergesort

di il
7 risposte

Shellsort VS Mergesort

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

7 Risposte

  • Re: Shellsort VS Mergesort

    E' un classico esempio di scarsa formazione sul problema complessità.

    (1) ci sono sempre dei coefficienti moltiplicativi che vengono di sovente ignorati, erroneamente.
    (2) al di là degli aspetti più tecnici (cioè cosa fa, che confronti, che spostamenti), che ricadono in esami complessi, ti pongo un problemino.

    Secondo te qual'è l'algoritmo più veloce per ordinare un certo vettore?
    Supponiamo per semplicità di interi.
    Rifletti prima di dare la risposta che ti hanno insegnato (tipicamente sbagliata)
  • Re: Shellsort VS Mergesort

    +m2+ ha scritto:


    E' un classico esempio di scarsa formazione sul problema complessità.

    (1) ci sono sempre dei coefficienti moltiplicativi che vengono di sovente ignorati, erroneamente.
    (2) al di là degli aspetti più tecnici (cioè cosa fa, che confronti, che spostamenti), che ricadono in esami complessi, ti pongo un problemino.

    Secondo te qual'è l'algoritmo più veloce per ordinare un certo vettore?
    Supponiamo per semplicità di interi.
    Rifletti prima di dare la risposta che ti hanno insegnato (tipicamente sbagliata)
    Secondo me è più veloce il mergesort...anche se non saprei come mostrarlo
  • Re: Shellsort VS Mergesort

  • Re: Shellsort VS Mergesort

    alefede96 ha scritto:


    +m2+ ha scritto:


    E' un classico esempio di scarsa formazione sul problema complessità.

    (1) ci sono sempre dei coefficienti moltiplicativi che vengono di sovente ignorati, erroneamente.
    (2) al di là degli aspetti più tecnici (cioè cosa fa, che confronti, che spostamenti), che ricadono in esami complessi, ti pongo un problemino.

    Secondo te qual'è l'algoritmo più veloce per ordinare un certo vettore?
    Supponiamo per semplicità di interi.
    Rifletti prima di dare la risposta che ti hanno insegnato (tipicamente sbagliata)
    Secondo me è più veloce il mergesort...anche se non saprei come mostrarlo
    Ecco, come prevedevo non ti hanno insegnato bene, ma è "normale".
    Supponi di dover ordinare due numeri X e Y.

    Applicheresti un mergesort? Uno shell sort?
    O faresti un confronto e basta?

    Cosa ti fa (o dovrebbe) pensare questo esempio?
  • Re: Shellsort VS Mergesort

  • Re: Shellsort VS Mergesort

    La VERA prova NON consiste nel fare i test con vettorini minuscoli, ma aumentare la dimensione del vettore:
    10,100,1.000,10.000,100.000,1.000.000,10.000.000,100.000.000,1.000.000.000 (sono girca 4/8 GB -) )
    Mappa i tempi per queste dimensioni e POI contronta i due algoritmi.
  • Re: Shellsort VS Mergesort

    migliorabile ha scritto:


    La VERA prova NON consiste nel fare i test con vettorini minuscoli, ma aumentare la dimensione del vettore:
    10,100,1.000,10.000,100.000,1.000.000,10.000.000,100.000.000,1.000.000.000 (sono girca 4/8 GB -) )
    Mappa i tempi per queste dimensioni e POI contronta i due algoritmi.
    Quindi per valutare come ordinare i due numeri X e Y faresti questo confronto?

    Burdèl nessuno spiega più la complessità asintotica, e quella ricorsiva?
    Evidentemente no
Devi accedere o registrarti per scrivere nel forum
7 risposte