Laboratorio di Informatica: Algoritmi e Strutture Dati

a.a. 2001/2002

Data: 09.02.2002 

Data consegna relazioni: 19.02.2002 (corso A); 20.02.2002 (corso B).

Si vuole studiare il comportamento in media dei seguenti algoritmi di ordinamento, in funzione della dimensione del vettore:

InsertionSort

QuickSort

stimando per ognuno di essi con intervallo di confidenza del 95% il tempo di esecuzione in media su vettori di lunghezze n pari a 10,20,50,100,200,500,1000,5000 (ed eventualmente altre nell'intervallo tra 10 e 5000).
Studiare nello stesso modo anche il comportamento in media di una variante di quicksort in cui su vettori di lunghezza minore di m si utilizza insertionsort, determinando sperimentalmente il valore ottimale di m.
VARIANTE: Per vettori di lunghezza minore di m arrestare l'esecuzione di quicksort ed aggiungere un'unica chiamata finale ad insertionsort.
Spiegare le eventuali relazioni tra i dati ottenuti nella prima e nella seconda parte.

Si deve consegnare una relazione analitica che comprenda:

1.obiettivi dell'esperimento;

2.metodologia dell'esperimento;

3.strumenti usati;

4.tabelle e grafici riepilogativi e comparativi;

5.conclusioni;

6.listati completi.

I gruppi possono consistere di al piu' due componenti.