Progetto di laboratorio di Algoritmi e Strutture Dati

di Sonia Dalla Costa

Obiettivi dell’esperimento:

Si vuole studiare il comportamento in media degli algoritmi di ordinamento InsertionSort e MergeSort in funzione della dimensione del vettore, stimando per ognuno di essi con intervallo di confidenza del 95% il tempo di esecuzione in media su vettori di lunghezze n pari a10,20,50,100,200,500,1000,5000.

Svolgimento della prova:

L’ ambiente di sviluppo adottato nella prova è Java version 1.4.1. I test sono stati effetuati su Intel Pentium 4 1.7 GHz con 256 Mb di memoria ram con sistema operativo Debian SID.

Metodologia dell’esperimento:

Per lo studio del comportamento dei due algoritmi di ordinamento (Insertionsort e MergeSort) per prima cosa viene calcolato il numero di ripetizioni necessarie per ottenere una misurazione significativa dei tempi (con un errore relativo percentuale inferiore all’ 5% ) e poi si passa alla misurazione dei tempi relativi all’inizializzazione dell’array e all’esecuzione degli algoritmi di ordinamento.Le misurazioni dei tempi sono state effettuate su 200 campioni di vettori di lunghezza variabile n (con n compreso tra 10 e 5000). Per il calcolo dei tempi medi infatti si dovrebbero generare n! vettori di lunghezza l e fare la media dei tempi ottenuti;questo non è possibile e quindi ci limitiamo a un campione di vettori che permette di garantire un risultato affidabile che è di 200 elementi. Dopo il calcolo dei tempi relativi ai vari campioni, vengono calcolati il tempo medio, la varianza e l’intervallo di confidenza.L’intevallo di confidenza (1-α ) deve essere al 95%. Abbiamo quindi:

)()2

1(1

nszcn

⋅−⋅=∆ α dove cn è la cardinalità del campione.

Infine, la formula per il calcolo della varianza è:

2

1

22 )](['),(1

)( nXEinXc

nscn

in

−= ∑=

Funzionamento del programma:

Il programma realizzato prende come argomento da riga di comando il numero di elementi dell’array da testare e il numero di ripetizioni necessarie per garantire un risultato affidabile (200 ripetizioni).All’inizio viene eseguito un semplice controllo sugli argomenti passati e poi inizia il programma.Nella prima parte viene calcolato il fattore di ripetizione che servirà per ridurre l’errore relativo delle misure. Per la misura dei tempi utilizzo il metodo getTime() che restituisce tempi in millisecondi.

2

Per limitare l’errore relativo all’5% devo misurare un evento di durata d, con δ tale che: 100:5 = δ :5 ovvero δ =100.L’esecuzione delle procedure di inizializzazione e di ordinamento dell’array verranno quindi ripetute n volte.Il fattore di ripetizione n viene calcolato una sola volta sulla procedura più breve e cioè su quella di inizializzazione del vettore.In un primo tempo viene fatta una stima per difetto e poi una per eccesso mediante due cicli while. Nel primo ciclo n viene raddoppiato ciclicamente fino a quando l’intervallo misurato supera δ . Alla fine del ciclo il fattore n sarà compreso tra l’intervallo [a,b]. Il secondo ciclo riduce questo intervallo attraverso una serie di divisioni per due. Al termine del ciclo b sarà una stima per eccesso del fattore di ripetizione con un errore di 5.Una volta determinato il fattore n si passa alla misura dei tempi di esecuzione degli algoritmi di ordinamento: viene inizializzato un vettore di lunghezza n con degli elementi casuali e viene misurato il tempo necessario per eseguire n volte l’algoritmo di ordinamento in esame. Una volta terminata la misurazione, si passa al prossimo vettore campione.Vengono effettuate nell’ordine le misurazioni dei tempi di esecuzione dell’algoritmo di inizializzazione, di InsertionSort,e di MergeSort e poi si ottengono i tempi medi, la varianza e l’intervallo di confidenza.

Codice:import java.util.*;

class LabASD {public static void main (String[] arg) {

/* Progetto di Laboratorio - Algoritmi e Strutture Dati */

System.out.println("-------------------------------------------------------");System.out.println("Progetto di laboratorio di Algoritmi e Strutture Dati");System.out.println("Componente del gruppo:Sonia Dalla Costa");System.out.println("-------------------------------------------------------");

/*I parametri passati tramite linea di comando sono due: il numero di elementi e il numero di campioni. Convalida dei parametri e assegnamento delle variabili globali */

/*Si verifica che il numero di parametri passati in input coincida con la sintassi del programma */

if (arg.length != 2) { /* Se gli argomenti sono piu` o meno di due... */System.out.println("Sintassi: java LabASD <numero di elementi> <numero di

campioni>");return; /* ...il programma termina */

}

try {size = Integer.parseInt(arg[0]); /* Si verifica che la dimensione dell'array sia

un intero */if (size < 2) { /* Si verifica che l'array contenga almeno 2 elementi */

System.out.println("L'array deve contenere almeno 2 elementi");

3

return; /* Se contiene meno di due elementi il programma termina */}

} catch (NumberFormatException e) { /* Se il parametro passato non e` un intero il programma termina... */

System.out.println("La dimensione dell'array dev'essere un intero"); /* ...restituendo l'errore */

}

try {samples = Integer.parseInt(arg[1]); /* Si verifica che il numero dei campioni

sia un intero */if (samples < 1) { /* Si verifica che ci sia almeno un test da eseguire */

System.out.println("Il test dev'essere eseguito su almeno un campione");

return; /* Se il numero di test e` minore di uno il programma termina */

}

} catch (NumberFormatException e) { /* Se il parametro passato non e` un intero il programma termina... */

System.out.println("Il numero di campioni dev'essere un intero"); /* ...restituendo l'errore */

}

/* Inizializzazione dell'array e chiamate delle funzioni */

Random generator = new Random();seed = generator.nextInt(); //inizializza il seme del generatore di numeri casualidata = new int[size];

findLoops();String M="MergeSort";String I="InsertionSort";findTime(I);findTime(M);

}

/* La funzione timeGetTime() calcola il tempo corrente e lo restituisce in millisecondi */

private static double timeGetTime() { Date time; time = new Date(); /* A ogni chiamata viene instanziato un nuovo oggetto Date */ return (double)time.getTime(); /* Viene restituito il tempo corrente in millisecondi

con un cast a double */}

/* La funzione findLoops() calcola il numero di ripetizioni necessarie per calcolare una stima con un errore

relativo limitato all'5% */

4

private static void findLoops() {double time1,time2; /* Dichiara due variabili double che conterranno i tempi */int a,b,numOfLoops; /* Dichiara due variabili intere che conterranno gli estremi e il

numero di ripetizioni */numOfLoops = 1; /* Inizializzazione del numero di ripetizioni */time1 = time2 = 0; /* Inizializzazione dei tempi */

/* Si determina una stima per eccesso e una per difetto del fattore di ripetizione */

while( (time2-time1) < delta) { /* Finche` non si misura un evento di durata almeno uguale a delta... */

numOfLoops *= 2; /* ...il fattore di ripetizione viene raddoppiato */time1 = timeGetTime(); for (int i = 1; i < numOfLoops; i++)

init(); /* Si calcolano i tempi per la procedura di inizializzazione */time2 = timeGetTime();

}a = numOfLoops / 2; /* Stima per difetto */b = numOfLoops; /* Stima per eccesso */System.out.println("Estremi dell'intervallo calcolato: [" + a + ", " + b + "]");

/*L'intervallo calcolato viene ridotto attraverso un processo di bisezione;Alla fine del ciclo b sarà una stima per eccesso del fattore di ripetizione con un errore

di 5 */

while( (b - a) >= 5) { /* Finche` l'errore non e` inferiore a 5... */numOfLoops = ((a+b)/2); /* ...l'intervallo viene dimezzato */time1 = timeGetTime(); for (int i = 1; i < numOfLoops; i++)

init(); /* Si calcolano i tempi per la procedura di inizializzazione */time2 = timeGetTime(); if (( time2 - time1) <= delta) /* Se la durata dell'evento non e` superiore a

delta */a = numOfLoops;

else b = numOfLoops;

} System.out.println("Fattore di ripetizione calcolato: " + numOfLoops); loops = numOfLoops; /* Assegna il risultato alla variabile globale contenente il

fattore di ripetizione */}

/* La funzione findTime(), utilizzando il fattore di ripetizione precedentemente trovato, restituisce in output la media la varianza e l'intervallo di confidenza calcolati per ciascuno degli algoritmi di ordinamento. Il test viene eseguito su un determinato numero di campioni contenuto nella variabile globale 'samples' */

public static void findTime(String algorithm) {double time1, time2, totalTime = 0, sqrTotalTime = 0, grossTime, netTime, tare;System.out.println("-----------------");System.out.println("[2] "+algorithm);

5

System.out.println("-----------------");for(int k = 0; k < samples; k++) { /* Per ciascuno dei campioni... */

System.out.print("Campione [" + (k+1) + "] :");time1 = timeGetTime(); for(int i = 0; i < loops; i++) { /* ...utilizzando il fattore di ripetizione

calcolato... */init(); /* ...viene calcolato il tempo necessario a inizializzare il

vettore... */if (algorithm.equals("InsertionSort")) { insertionSort(0, size -1); /* ...e a ordinarlo tramite InsertionSort. */}else{ mergesort();}

} time2 = timeGetTime(); grossTime = time2 - time1; /* Si ottiene così il tempo lordo di esecuzione */ time1 = timeGetTime(); for(int i = 0; i < loops; i++)

init(); /* Viene quindi calcolato il tempo necessario alla sola inizializzazione... */

time2 = timeGetTime();tare = time2 - time1; /* ...che viene sottratto al tempo lordo ottenendo la tara

*/netTime = (grossTime - tare) / loops; /* Viene infine calcolato il tempo netto

medio... */System.out.println(" " + netTime + " millisecondi");totalTime += netTime; /* ...che viene quindi sommato al tempo

complessivo... */sqrTotalTime += (netTime * netTime); /* ...e al quadrato del tempo

complessivo */} double averageTime = totalTime / samples; /* Vengono calcolati: il tempo medio

complessivo... */double varianza = (sqrTotalTime - samples * averageTime * averageTime) /

(samples); /*... la varianza... */double error = 1.96 * ( Math.sqrt(varianza / samples) ); /* ...e l'intervallo di

confidenza */double delta =(1/(Math.sqrt(samples)))*1.96*(Math.sqrt(varianza)); double sx = averageTime-delta;double dx = averageTime+delta;System.out.println("Lunghezza = "+ size);

System.out.println("Ripetizioni = "+ samples); System.out.println("Varianza = "+ varianza);System.out.println("Media = "+ averageTime +" +/- " + error); System.out.println("Intervallo di confidenza: "+sx+" , "+dx);System.out.println();

}

6

/* La funzione init() inizializza il vettore utilizzando il generatore di numeri casuali istanziato come variabile globale. In questo modo ad ogni esecuzione del programma si ottiene un generatore inizializzato con un seme basato sul tempo corrente */

public static void init() {for (int i = 0; i < size; i++) /* Per ogni elemento del vettore */

data[i] = (int)(65536*rand()); /* Viene generato un valore casuale compreso tra 0 e 2^16 -1 */

}

/* La funzione insertionSort(int p,int q) ordina l'array secondo il corrispondente algoritmo */

public static void insertionSort(int p,int q) { int j, i; int tmp; for(j = p + 1; j <= q; j++) { /* Per ogni elemento del vettore */

tmp = data[j]; /* Il valore corrente viene salvato nella variabile tmp */ for(i = j-1; (i>=p) && (data[i]>tmp); i--) { /* Se l'elemento non è in ordine...

*/data[i+1] = data[i]; } /* Viene scambiato */data[i+1] = tmp; /* Il valore temporaneo viene inserito nella posizione

corretta */}

} /* Nella variabile temp vengono salvati i valori */ private static int[] temp;

public static void mergesort(){ temp=new int[size]; mergeSort(1,size-1);}

/* La funzione mergeSort(int p, int q) ordina l’array secondo il corrispondente algoritmo */public static void mergeSort(int p, int q) { int r; if (p < q) { /* Se il vettore contiene almeno un elemento calcola in r l’indice della metà

del vettore… */r = (int)Math.floor((p + q) / 2);mergeSort(p,r);mergeSort(r + 1,q); /* Richiama ricorsivamente la procedura fondendo i due

sottovettori (p,r) e (r + 1, q) */Merge(p,q,r); } /* Chiama la procedura Merge per fondere e ordinare i due

sottovettori */}private static void Merge(int p, int q, int r) { /* La procedura Merge fonde e ordina i

sottovettori */ int i=p,j=q+1,k=0,h; /* int[] temp=new int[size-1]; while (i<=q && j<=r) { /* Con questo ciclo legge i valori dei due sottovettori e li riporta

nell’ordine giusto nella variabile temp */ if (data[i]<data[j]) { temp[k]=data[i]; i++;

7

}else{ temp[k]=data[j]; j++; } k++;

} if (j <=r) { /* Quando uno dei due sottovettori è stato ordinato, vengono copiati nella

variabile temp i valori dell’altro sottovettore, già ordinati */ for (h=j; h<=r; h++) { /* Se gli elementi del secondo sottovettore sono stati ordinati,

si copiano gli elementi del secondo sottovettore */ temp[k]=data[h]; k++; }}

else { for (h=i; h<=q; h++) { /* se gli elementi del primo sottovettore sono stati ordinati, si

copiano gli elementi del primo sottovettore */ temp[k]=data[h]; k++; }}

for (h=0; h<k; h++) { /* Vengono copiati gli elementi ordinati presenti nella variabile temp nel vettore di partenza data */

data[h+p]=temp[h]; }}

public static double rand() {final int a = 16807; /* Costanti per il calcolo dei numeri casuali */final int m = 2147483647;final int q = 127773;final int r = 2836;double lo, hi, test;hi = (int)(seed / q); /* Procedura che calcola i numeri casuali */lo = seed - q * hi;test = a * lo - r * hi;if (test < 0)

seed = test + m;else

seed = test;return (seed / m);

}/* Variabili globali */

static int size; /* Dimensione dell'array */static int samples; /* Numero di campioni */static int loops; /* Fattore di ripetizione */static int data[]; /* Array da ordinare */static final int delta = 100; /* 100 : 1 = delta : 1 -> delta = 100 */private static double seed;

}

8

Analisi del codice:

-Generatore di numeri casuali:Al generatore di numeri casuali viene fornito un seme (seed), cioè un numero che dev’ essere sempre diverso, altrimenti sarebbe sempre lo stesso e poi viene generata una sequenza determinata dal seme di numeri razionali compresi tra 0 e 1.

public static double rand() {final int a = 16807;final int m = 2147483647;final int q = 127773;final int r = 2836;double lo, hi, test;hi = (int)(seed / q);lo = seed - q * hi;test = a * lo - r * hi;if (test < 0)

seed = test + m;else

seed = test;return (seed / m);

}

-Algoritmo InsertionSort:L’algoritmo InsertionSort per ordinare il vettore considera l’elemento i-esimo e lo confronta con gli elementi (i-esimi-1) già ordinati per poterlo inserire nella corretta posizione; la complessità di questo algoritmo nel caso peggiore è n2.

public static void insertionSort(int p,int q) { int j, i; int tmp; for(j = p + 1; j <= q; j++) { /* Per ogni elemento del vettore */

tmp = data[j]; /* Valore corrente viene salvato nella variabile tmp */ for(i = j-1; (i>=p) && (data[i]>tmp); i--) { /* Se l'elemento non e` in ordine...

*/data[i+1] = data[i]; } /* Viene scambiato */data[i+1] = tmp; /* Il valore temporaneo viene inserito nella posizione

corretta */}

}

- Algoritmo MergeSort:Il MergeSort ordina il vettore nel seguente modo: all’inizio il vettore viene diviso in due sottovettori che poi vengono ordinati ricorsivamente; alla fine si richiama la procedura Merge che fonde i due sottovettori ordinati da mergeSort; la complessità di tale algoritmo nel caso peggiore è n log n.

9

public static void mergeSort(int p, int q) { int r; if (p < q) {

r = (int)Math.floor((p + q) / 2);mergeSort(p,r);mergeSort(r + 1,q);Merge(p,q,r); }

}

private static void Merge(int p, int q, int r) { int i=p,j=q+1,k=0,h; int[] temp=new int[size-1]; while (i<=q && j<=r) {

if (data[i]<data[j]) { temp[k]=data[i]; i++; }else{ temp[k]=data[j]; j++; } k++;

} if (j <=r) {

for (h=j; h<=r; h++) { temp[k]=data[h]; k++; }}

else { for (h=i; h<=q; h++) { temp[k]=data[h]; k++; }}

for (h=0; h<k; h++) { data[h+p]=temp[h];

}}

10

Tabelle e grafici riepilogativi e comparativi:

Tabella dati dell’algoritmo InsertionSort

Lunghezza vettore Varianza Media Intervallo di confidenza10 1,231847*10-8 0,011364 +/- 2,175377*10-5 0,0113424, 0,011385920 6,184681*10-8 0,036843 +/- 4,874327*10-5 0,0367949, 0,036899250 5,177673*10-7 0,199650 +/- 1,410338*10-4 0,1199509, 0,1997913

100 3,139077 0,759063 +/- 3,472618*10-4 0,758716, 0,759410200 8,264828 2,958225 +/- 0,001781 2,956443, 2,960007500 0,00537777 18,197023 +/- 0,014373 18,182650, 18,211397

1000 0,0325611 72,858064 +/- 0,035367 72,822696, 72,8934215000 20,070906 1803,477142 +/- 0,878091 1802,59905, 1804,355233

Grafico dell’InsertionSort

Grafico dell'InsertionSort

0

500

1000

1500

2000

10 20 50 100

200

500

1000

5000

Lunghezza vettore

Tem

po

imp

ieg

ato

InsertionSort

OSSERVAZIONI: Come si può notare anche dal grafico il tempo impiegato dall’InsertionSort per ordinare un vettore aumenta vertiginosamente se il vettore da ordinare è grande.

Tabella dati del MergeSort

Lunghezza vettore Varianza Media Intervallo di confidenza

10 3,071465*10-7 0,0471768 +/- 1,086224*10-4 0,04706, 0,047285520 3,147967*10-6 0,114206 +/- 3,47753*10-6 0,113859, 0,11455450 4,859203*10-6 0,349682 +/- 4,320545*10-4 0,349249, 0,350114

100 2,130889*10-5 0,846269 +/- 9,047665*10-4 0,845365, 0,847174200 8,8901144*10-5 2,175677 +/- 0,001848 2,173829, 2,177525500 0,001247 8,752857 +/- 0,006923 8,745933, 8,759780

1000 0,00599018 27,84217741 +/- 0,0151696 27,827007, 27,8573475000 0,45244081 543,747142 +/- 0,131836 543,615305, 543,87897

11

Grafico del MergeSort

Grafico del MergeSort

0

100

200

300

400

500

600

10 20 50 100

200

500

1000

5000

Lunghezza del vettore

Te

mp

o i

mp

ieg

ato

MergeSort

OSSERVAZIONI:Come si può notare anche dal grafico il tempo impiegato dal MergeSort per ordinare un vettore aumenta vertiginosamente se il vettore da ordinare è grande.

Confronto dei tempi impiegati dall’InsertioSort e dal MergeSort per ordinare il vettrore n

Lunghezza vettore (n)

Tempo impiegato dall’InsertionSort per ordinare il vettore

Tempo impiegato dal MergeSort per ordinare il

vettore10 0,011364 +/- 2,175377*10-5 0,0471768 +/- 1,086224*10-4

20 0,036843 +/- 4,874327*10-5 0,114206 +/- 3,47753*10-6

50 0,199650 +/- 1,410338*10-4 0,349682 +/- 4,320545*10-4

100 0,759063 +/- 3,472618*10-4 0,846269 +/- 9,047665*10-4

200 2,958225 +/- 0,001781 2,175677 +/- 0,001848500 18,197023 +/- 0,014373 8,752857 +/- 0,006923

1000 72,858064 +/- 0,035367 27,84217741 +/- 0,01516965000 1803,477142 +/- 0,878091 543,747142 +/- 0,131836

12

Grafici di confronto tra InsertionSort e MergeSort

Confronto fra i due algoritmi presi in considerazione per vettori piccoli

Confronto InsertionSort e MergeSort

0

0,5

1

1,5

2

2,5

3

3,5

10 20 50 100 200

Lunghezza del vettore

Tem

po

im

pie

gat

o

MergeSort

InsertionSort

Punto d’intersezione tra InsertionSort e MergeSort

Punto d'intersezione tra InsertionSort e MergeSort

0

0,5

1

1,5

2

2,5

3

3,5

0 50 100 150 200 250

Lunghezza del vettore

Tem

po

imp

ieg

ato

MergeSort

InsertionSort

OSSERVAZIONI:I grafici e le tabelle sopra riportati ci mostrano che l’algoritmo MergeSort risulta essere più lento nel calcolo del tempo per vettori di piccole dimensioni, a differenza dell’InsertionSort, mentre risulta essere molto più veloce nel calcolo del tempo impiegato per ordinare vettori di grandi dimensioni.

13

Funzionamento del programma:Fondendo i due algoritmi possiamo ottenerne un altro più potente in grado di calcolare più rapidamente i tempi di ordinamento di un vettore.Il “nuovo” algoritmo, che chiamo OptimizeSort, utilizza l’algoritmo dell’InsertionSort per ordinare i vettori con lunghezza inferiore a 110 elementi in quanto quest’ultimo risulta essere più efficace rispetto al MergeSort nel calcolo dei tempi di ordinamento; quando il vettore supera queste dimensioni utilizzo l’algoritmo MergeSort che risulta essere migliore dell’InsertionSort.

Codice:

import java.util.*;

class Ultimo {public static void main (String[] arg) {

/* Progetto di Laboratorio - Algoritmi e Strutture Dati */

System.out.println();System.out.println("Progetto di laboratorio di Algoritmi e Strutture Dati");System.out.println("Sonia Dalla Costa");System.out.println();

/* I parametri passati tramite linea di comando sono due: il numero di elementi e il numero di campioni. Convalida dei parametri e assegnamento delle variabili globali *//* Si verifica che il numero di parametri passati in input coincida con la sintassi del programma */

if (arg.length != 2) { /* Se gli argomenti sono piu` o meno di due... */System.out.println("Sintassi: java LabASD <numero di elementi>

<numero di campioni>");return; /* ...il programma termina */

}

try {size = Integer.parseInt(arg[0]); /* Si verifica che la dimensione

dell'array sia un intero */if (size < 2) { /* Si verifica che l'array contenga almeno 2 elementi */

System.out.println("L'array deve contenere almeno 2 elementi"); return; /* Se contiene meno di due elementi il programma

termina */}

} catch (NumberFormatException e) { /* Se il parametro passato non e` un intero il programma termina... */

System.out.println("La dimensione dell'array dev'essere un intero"); /* ...restituendo l'errore */

}

14

try {samples = Integer.parseInt(arg[1]); /* Si verifica che il numero dei

campioni sia un intero */if (samples < 1) { /* Si verifica che ci sia almeno un test da eseguire */

System.out.println("Il test dev'essere eseguito su almeno un campione");

return; /* Se il numero di test e` minore di uno il programma termina */

}

} catch (NumberFormatException e) { /* Se il parametro passato non è un intero il programma termina... */

System.out.println("Il numero di campioni dev'essere un intero"); /* ...restituendo l'errore */

}

/* Inizializzazione dell'array e chiamate delle funzioni */

Random generator = new Random();seed = generator.nextInt(); /* inizializza il seme del generatore di numeri

casuali */data = new int[size];

findLoops();String M="MergeSort"; /* Stringhe che indicano che algoritmo è in utilizzo */String I="InsertionSort";

String O="optimizeSort";findTime(I);findTime(M);findTime(O);

}

/* La funzione timeGetTime() calcola il tempo corrente e lo restituisce in millisecondi */

private static double timeGetTime() { Date time; time = new Date(); /* A ogni chiamata viene instanziato un nuovo oggetto

Date */ return (double)time.getTime(); /* Viene restituito il tempo corrente in

millisecondi con un cast a double */}

/* La funzione findLoops() calcola il numero di ripetizioni necessarie per calcolare una stima con un errore relativo limitato all'5% */

private static void findLoops() {double time1,time2; /* Dichiara due variabili double che conterranno i tempi */int a,b,numOfLoops; /* Dichiara due variabili intere che conterranno gli

estremi e il numero di ripetizioni */numOfLoops = 1; /* Inizializzazione del numero di ripetizioni */time1 = time2 = 0; /* Inizializzazione dei tempi */

15

/* Si determina una stima per eccesso e una per difetto del fattore di ripetizione */

while( (time2-time1) < delta) { /* Finchè non si misura un evento di durata almeno uguale a delta... */

numOfLoops *= 2; /* ...il fattore di ripetizione viene raddoppiato */time1 = timeGetTime(); for (int i = 1; i < numOfLoops; i++) init(); /* Si calcolano i tempi per la procedura di inizializzazione */time2 = timeGetTime();

}a = numOfLoops / 2; /* Stima per difetto */b = numOfLoops; /* Stima per eccesso */System.out.println("Estremi dell'intervallo calcolato: [" + a + ", " + b + "]");

/* L'intervallo calcolato viene ridotto attraverso un processo di bisezione. Alla fine del ciclo b sarà una stima per eccesso del fattore di ripetizione con un errore di 5 */

while( (b - a) >= 5) { /* Finche` l'errore non e` inferiore a 5... */numOfLoops = ((a+b)/2); /* ...l'intervallo viene dimezzato */time1 = timeGetTime(); for (int i = 1; i < numOfLoops; i++)

init(); /* Si calcolano i tempi per la procedura di inizializzazione */

time2 = timeGetTime(); if (( time2 - time1) <= delta) /* Se la durata dell'evento non è superiore

a delta */a = numOfLoops;

else b = numOfLoops;

} System.out.println("Fattore di ripetizione calcolato: " + numOfLoops); loops = numOfLoops; /* Assegna il risultato alla variabile globale contenente

il fattore di ripetizione */} /* La funzione findTime(), utilizzando il fattore di ripetizione precedentemente

trovato, restituisce in output la media la varianza e l'intervallo di confidenza calcolati per ciascuno degli algoritmi di ordinamento. Il test viene eseguito su un determinato numero di campioni contenuto nella variabile globale 'samples' */

public static void findTime(String algorithm) {double time1, time2, totalTime = 0, sqrTotalTime = 0, grossTime, netTime,

tare;System.out.println("-----------------");System.out.println("[*] "+algorithm);System.out.println("-----------------");for(int k = 0; k < samples; k++) { /* Per ciascuno dei campioni... */

System.out.print("Campione [" + (k+1) + "] :");time1 = timeGetTime(); for(int i = 0; i < loops; i++) { /* ...utilizzando il fattore di ripetizione

calcolato... */init(); /* ...viene calcolato il tempo necessario a inizializzare il

vettore... */

16

if (algorithm.equals("InsertionSort")) { insertionSort(0, size -1); /* ...e a ordinarlo tramite

InsertionSort. */}if (algorithm.equals("MergeSort")){ /* o tramite MergeSort */ mergesort();}else{ optimizeSort();}

} time2 = timeGetTime(); grossTime = time2 - time1; /* Si ottiene così il tempo lordo di

esecuzione */ time1 = timeGetTime(); for(int i = 0; i < loops; i++)

init(); /* Viene quindi calcolato il tempo necessario alla sola inizializzazione... */

time2 = timeGetTime();tare = time2 - time1; /* ...che viene sottratto al tempo lordo ottenendo

la tara */netTime = (grossTime - tare) / loops; /* Viene infine calcolato il tempo

netto medio... */System.out.println(" " + netTime + " millisecondi");totalTime += netTime; /* ...che viene quindi sommato al tempo

complessivo... */sqrTotalTime += (netTime * netTime); /* ...e al quadrato del tempo

complessivo */} double averageTime = totalTime / samples; /* Vengono calcolati: il tempo

medio complessivo... */double varianza = (sqrTotalTime - samples * averageTime * averageTime) /

(samples); /*... la varianza... */double error = 1.96 * ( Math.sqrt(varianza / samples) ); /* ...e l'intervallo di

confidenza */double delta =(1/(Math.sqrt(samples)))*1.96*(Math.sqrt(varianza)); double sx = averageTime-delta;double dx = averageTime+delta;System.out.println("Lunghezza = "+ size);

System.out.println("Ripetizioni = "+ samples); System.out.println("Varianza = "+ varianza);System.out.println("Media = "+ averageTime +" +/- " + error); System.out.println("Intervallo di confidenza: "+sx+" , "+dx);System.out.println();

}

/* La funzione init() inizializza il vettore utilizzando il generatore di numeri casuali istanziato come variabile globale. In questo modo ad ogni esecuzione del programma si ottiene un generatore inizializzato con un seme basato sul tempo corrente */

public static void init() {for (int i = 0; i < size; i++) /* Per ogni elemento del vettore */

17

data[i] = (int)(65536*rand()); /* Viene generato un valore casuale compreso tra 0 e 2^16 -1 */

}public static void insertionSort(int p,int q) {

int j, i; int tmp; for(j = p + 1; j <= q; j++) { /* Per ogni elemento del vettore */

tmp = data[j]; /* Valore corrente viene salvato nella variabile tmp */ for(i = j-1; (i>=p) && (data[i]>tmp); i--) { /* Se l'elemento non è in

ordine... */data[i+1] = data[i]; } /* Viene scambiato */data[i+1] = tmp; /* Il valore temporaneo viene inserito nella posizione

corretta */}

} private static int[] temp; /* Algoritmo del MergeSort */public static void mergesort(){ temp=new int[size]; mergeSort(1,size-1);}public static void mergeSort(int p, int q) { int r; if (p < q) {

r = (int)Math.floor((p + q) / 2);mergeSort(p,r);mergeSort(r + 1,q);Merge(p,q,r); }

}public static void optimizeSort() {

temp=new int[size];mescSort(1,size-1);

} public static void mescSort(int p, int r) {

if ((r-p)<110) { /* Se la lunghezza del vettore è inferiore a 110... */ int j, key,i; /* ...il vettore viene ordinato con InsertionSort */ for (j=p; j<=r; j++) {

key=data[j];i=j-1;while (i>=p && data[i]>key) { data[i+1]=data[i]; i--;}data[i+1]=key;

}}else{ /*...altrimenti ordina il vettore con MergeSort */ int q=(p+r)/2; mescSort(p,q); mescSort(q+1,r); Merge(p,q,r);}

}

18

private static void Merge(int p, int q, int r) { /* Algoritmo del MergeSort */ int i=p,j=q+1,k=0,h; int[] temp=new int[size-1]; while (i<=q && j<=r) {

if (data[i]<data[j]) { temp[k]=data[i]; i++; }else{ temp[k]=data[j]; j++; } k++;

} if (j <=r) {

for (h=j; h<=r; h++) { temp[k]=data[h]; k++; }}

else { for (h=i; h<=q; h++) { temp[k]=data[h]; k++; }}

for (h=0; h<k; h++) { data[h+p]=temp[h];

}}

/* Generatore di numeri casuali */public static double rand() { /* Costanti per il calcolo dei numeri casuali */

final int a = 16807;final int m = 2147483647;final int q = 127773;final int r = 2836;double lo, hi, test;hi = (int)(seed / q); Procedura che calcola i numeri casuali */lo = seed - q * hi;test = a * lo - r * hi;if (test < 0)

seed = test + m;else

seed = test;return (seed / m);

}/* Variabili globali */

static int size; /* Dimensione dell'array */static int samples; /* Numero di campioni */static int loops; /* Fattore di ripetizione */static int data[]; /* Array da ordinare */static final int delta = 100; /* 100 : 1 = delta : 1 -> delta = 100 */private static double seed;

19

static int f; }

Tabelle e grafici riepilogativi e comparativi:Tabella dati dell’algoritmo OptimizeSort

Lunghezza vettore Varianza Media Intervallo di confidenza

10 2,617080*10-8 0,011151 +/- 3,170768*10-5 0,011119, 0,01182920 1,215063*10-7 0,035604 +/- 6,832120*10-5 0,035536,

0,00335672650 8,0895136*10-7 0,196115 +/- 1,762857 0,195939, 0,196291

100 5,663683*10-6 0,754395 +/-4,664504 0,753928, 0,754861200 1,622085*10-5 1,645000 +/-7,893922 1,644210, 1,645789500 1,413754*10-4 3,467272 +/- 0,006491 3,241876, 3,610087

1000 1,994437 7,712962 +/- 0,017768 7,528374,8,4618495000 31,231388 63,294999+/- 1,549054 61,367612, 65,465721

Grafico dell’OptimizeSort

OptimizeSort

0

50

100

150

200

10 20 50 100 200 500 1000 5000

Lunghezza del vettore

Tem

po

im

pie

gat

o

OptimizeSort

Confronto dei tempi impiegati dall’InsertionSort, dal MergeSort e dall’OptimizeSort per ordinare il vettore n

n Tempo impiegato dall’InsertionSort per ordinare il vettore

Tempo impiegato dal MergeSort per ordinare il vettore

Tempo impiegato dal OptimizeSort per ordinare il vettore

10 0,011364 +/- 2,175377*10-5 0,0471768 +/- 1,086224*10-4 0,011151 +/- 3,170768*10-5

20 0,036843 +/- 4,874327*10-5 0,114206 +/- 3,47753*10-6 0,035604 +/- 6,832120*10-5

50 0,199650 +/- 1,410338*10-4 0,349682 +/- 4,320545*10-4 0,196115 +/- 1,762857100 0,759063 +/- 3,472618*10-4 0,846269 +/- 9,047665*10-4 0,754395 +/-4,664504200 2,958225 +/- 0,001781 2,175677 +/- 0,001848 1,645000 +/-7,893922500 18,197023 +/- 0,014373 8,752857 +/- 0,006923 3,467272 +/- 0,006491

1000 72,858064 +/- 0,035367 27,84217741 +/- 0,0151696 7,712962 +/- 0,0177685000 1803,477142 +/- 0,878091 543,747142 +/- 0,131836 63,294999+/- 1,549054

20

Grafici di confronto tra InsertionSort, MergeSort e OptimizeSort

Grafico comparativo

0

500

1000

1500

2000

10 20 50 100 200 500 1000 5000

Lunghezza del vettore

Tem

po

im

pie

gato

InsertionSort

MergeSort

OptimizeSort

Confronto fra i tre algoritmi presi in considerazione per vettori piccoli

Grafico comparativo 1

0

0,5

1

1,5

2

2,5

3

3,5

10 20 50 100 200

Lunghezza del vettore

Tem

po

im

pie

gat

o

InsertioSort

MergeSort

OptimizeSort

CONCLUSIONI:

Dai grafici e dalle tabelle osserviamo che l’OptimizeSort risulta essere più efficiente rispetto gli altri due algoritmi nel calcolo del tempo sia per vettori di piccole dimensioni che per quelli di grandi dimensioni.Come si può notare dalle tabelle e dai grafici, ogni algoritmo ha dei pregi: l’InsertionSort è rapido nel calcolo dei tempi di ordinamento per vettori di piccole dimensioni, il MergeSort, invece, è più rapido per vettori di grandi diemensioni, mentre l’OptimizeSort è efficace sia con vettori di piccoli che di grandi dimensioni.

21