Laboratorio di Informatica: Algoritmi e Strutture Dati

a.a. 2000/20001

Progetto n. 1

Data: 10.01.2001 (Rev. 14.01.2001)

Data consegna relazioni: 08.02.2001

L'algoritmo di ordinamento ShellSort e' costituito dalla seguente generalizzazione di InsertionSort (espressa in pseudocodice nello stile di Cormen et al.):

foreach h in {vd,vd-1, ..., 1}


   do for j <- h+1 to length[A]


      do k <- A[j]


         i <- j-h


         while i > 0 and A[i] > k


            do A[i+h] <- A[i]


               i <- i-h


         A[i+h] <- k

Per ottenere un programma di ordinamento a partire da questo schema e' necessario fissare i valori assunti da h (cioe' la sequenza {vd,vd-1, ..., 1}). Il fatto che tale sequenza contenga sempre 1 assicura che l'algoritmo si comportera' sempre almeno come InsertionSort nelle sue ultime passate. Il tempo di calcolo di ShellSort dipende ovviamente dalla sequenza scelta per {vd,vd-1, ..., 1}. Sono state studiate in letteratura varie possibilita', tra le quali:

  1. tutti gli interi della forma (3i -1)/2, per i = t, t-1, ..., 1 (il valore t viene determinato in modo da essere il primo valore per cui (3t+1 -1)/2 > length[A]. I primi valori della sequenza sono: ..., 1093, 364, 121, 40, 13, 4, 1.
  2. tutti gli interi della forma 2i3j minori o uguali a length[A]. I primi valori della sequenza sono: ..., 9, 8, 6, 4, 3, 2, 1.
  3. i valori determinati dal seguente schema ricorsivo:

vd+1 = length[A]; vk-1 = trunc[ (5*vk-1)/11] se vk >= 5; vk-1 = 1 se vk <5.

 

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

InsertionSort

ShellSort, per le tre scelte (1), (2), e (3) sopra descritte

QuickSort

HeapSort

A tal fine si stimino con un intervallo di confidenza del 95% i valori medi dei seguenti due parametri:

Cn: numero di confronti utilizzati per ordinare n numeri

Sn: numero di scambi utilizzati per ordinare n numeri

per tutti gli algoritmi citati e per almeno i seguenti valori di n: 10,20,50,100,500,1000, 5000.

E' ammesso l'uso dei seguenti linguaggi di programmazione: Pascal, C, C++, Java.

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' tre componenti.