RELAZIONE ALGORITMI E STRUTTURE DATI

Progetto 1

Gruppo composto daForgiarini Stefano eRocchi Mauro

1. Introduzione

Lo scopo dell'esperimento è valutare la complessità di alcuni classici algoritmi di ordinamento (e di alcune loro varianti) in modo empirico al fine di verificare la corretezza dei risultati teorici.

Gli algoritmi analizzati sono:– BubbleSort

● Versione non ottimizzata● Versione ottimizzata

– MergeSort– QuickSort

● Versione a doppia ricorsione (originale)● Versione a ricorsione di coda (singola chiamata ricorsiva)● Versione iterativa

– InsertionSort– Algoritmi misti

● QuickSort + InsertionSort● QuickSort + BubbleSort (ottimizzato)

Per ognuno di questi algoritmi si vuole stimare il tempo di esecuzione nel caso medio su vettori di dimensione variabile.Con i dati ottenuti dagli esperimenti verranno prodotti i grafici che permetteranno di verificare il comportamento asintotico di ogni algoritmo.

2. Descrizione e analisi degli algoritmi

Tutti gli algoritmi analizzati operano su array di interi. Saranno calcolati i tempi nel caso medio su array di dimensione n pari a 10, 20, 50, 100, 200, 500, 1000, 2500 e 5000. Tutti gli algoritmi di ordinamento hanno lo stesso prototipo  void Algo(int array[], int p, int r) . Questo significa che ad ogni algoritmo vengono passati tre argomenti: un array di interi, un intero p che rappresenta l'indice del primo elemento dell'array e un altro intero r, che indica la dimensione dell'array (l'ultimo indice del vettore è dunque r – 1). 

2.1 BubbleSort

L'algoritmo,   basato   sul   confronto,   opera   scambiando   ripetutamente   gli   elementi   adiacenti   non ordinati.  Esso  non  necessita  di  memoria   aggiuntiva   (gli   scambi   infatti   avvengono  direttamente all'interno dell' array di partenza), dunque è un algoritmo in­place. 

2.1.1 Non ottimizzato

void BubbleSort(int array[], int p, int r){ int size = r – p;

for (int i = 0; (i < size - 1); i++) { for (int j = 0; j < size - i - 1; j++) if (array[j + 1] < array[j]) { Swap( &array[j], &array[j + 1] ); } }}

Il BubbleSort (ordinamento a bolle) consiste in un ciclo for innestato all'interno di un altro ciclo for. Il for loop esterno garantisce che il for loop interno venga ripetuto size – 1 volte. Il ciclo interno è quello che fa il grosso del lavoro: infatti, se l'elemento in A[j] è maggiore di quello in A[j + 1], viene eseguita un'operazione di swap, che scambia di posto i due elementi all'interno dell'array. Le operazioni di confronto ed eventualmente quelle di scambio verranno ripetute size – i – 1 volte. In questo modo, man mano che cresce il valore della variabile contatore i, diminuisce il numero dei confronti e scambi da effettuare. Questo perchè ad ogni iterazione i (a partire da i=0) del ciclo for esterno,   è   garantito   che   l'elemento   “più   pesante”   dell'array   viene   memorizzato   in   posizione A[size – i  – 1]. In questo modo, alla successiva iterazione, basterà  confrontare gli  elementi  del sottoarray A[0 ... size – i – 1], con i che è stato incrementato di un'unità.   La complessità di BubbleSort è quadratica (O(n2  )) nel caso pessimo, medio e migliore. Non esiste infatti alcuna differenza (sul piano asintotico) tra i tre casi, in quanto vengono effettuati sempre lo stesso numero di confronti. 

2.1.2 Ottimizzato

Il BubbleSort originale, sebbene sia molto semplice, è uno degli algoritmi meno efficienti poiché richiede   O(n2  )   confronti.   Per   migliorare   le   sue   prestazioni   viene   proposta   la   seguente ottimizzazione.

void BubbleSortOtt(int array[], int p, int r){ int j, last, k; k = r - 1; while (k >= 0) { last = -1; for (j = 0; j < k; j++) { if (array[j] > array[j + 1]) { Swap(&array[j], &array[j + 1]); last = j; } } k = last; }}

Questo algoritmo nasce dalle due seguenti   intuizioni:  1)  se durante un ciclo for esterno non si effettuano scambi, allora l'array è già ordinato; 2) se durante un ciclo for interno non si effettuano scambi in posizione maggiore di k, allora in nessun ciclo for esterno successivo si effettueranno scambi in posizione maggiore di k (questo significa che il sottoarray A[k+1...r­1] è già ordinato in modo crescente). Si utilizzerà dunque la variabile last per tenere traccia dell'indice j dell'elemento che viene scambiato. In questo modo, quando si esce dal ciclo for, la variabile last conterrà l'indice dell'ultimo   elemento   scambiato.   La     variabile   k   assumerà   tale   valore   (si   è   così   sicuri   che   il sottoarray   A[k+1...r­1]   sia   già   ordinato)   in   modo   da   potersi   limitare   al   sottoarray   A[0...k]. L'algoritmo termina quando il  valore di  k è  negativo (quando k = last  = ­1),  cioè  quando non vengono più effettuati degli scambi. Un'ultima notazione: la variabile last viene inizializzata a ­1 affinchè,   se   l'array   è   già   ordinato   fin   dall'inizio,   l'algoritmo   termini   dopo   solo   una   “passata” dell'array. La complessità è dunque O(n) nel caso migliore (array già ordinato in modo crescente) ma sempre O(n2  ) in quello peggiore (array ordinato in modo decrescente); anche nel caso medio BubbleSortOtt risulta avere un tempo d'esecuzione pari a O(n2 ).  

2.2 MergeSort

L'algoritmo di ordinamento MergeSort si fonda sul principio divide et impera (dividi e conquista), che  consiste  nel   suddividere   il   problema originale   in   sottoproblemi  di  dimensioni  più   piccole, risolvere i sottoproblemi in modo ricorsivo ed infine combinare  le soluzioni di questi per creare una soluzione del problema originale. Il  MergeSort è  un algoritmo efficiente per quanto riguarda il tempo di esecuzione, ma ha il difetto di non essere in­place. La procedura Merge infatti, come si può notare dal codice, crea due sottoarray d'appoggio (L ed R) per poi fonderli in maniera ordinata in A.  

void MergeSort(int array[], int p, int r){ if (r - p > 1) { size_t q = (p + r) / 2; MergeSort(array, p, q); MergeSort(array, q, r); Merge(array, p, q, r); }}

void Merge(int A[], int p, int q, int r)

{ int n1 = q - p, n2 = r - q;

int *L = new int[n1 + 1], *R = new int[n2 + 1];

int i, j;

for (i = 0; i < n1; ++i) L[i] = A[p + i];

for (i = 0; i < n2; ++i) R[i] = A[q + i];

L[n1] = INFINITE; R[n2] = INFINITE; i = j = 0; for (int k = p; k < r; ++k) { if (L[i] <= R[j]) A[k] = L[i++]; else A[k] = R[j++]; }

delete [] L; delete [] R;}

MergeSort   opera   in   questo  modo:   1)   divide   la   sequenza  degli   n   elementi   da  ordinare   in   due sottosequenze di n/2 elementi ciascuna; 2) ordina le due sottosequenze in modo ricorsivo utilizando l'algoritmo MergeSort; 3) fonde le due sottosequenze ordinate per generare la sequenza ordinata. La ricorsione tocca il fondo quando la sequenza da ordinare ha lunghezza 1 (cioè quando p è maggiore o uguale ad r – 1). In questo caso ogni sequenza è logicamente ordinata e solo in ora possono essere eseguite le varie chiamate di Merge, che ha il compito di fondere due sottosequenze ordinate di elementi (quelle che sono state copiate nei vettori di supporto L ed R) in un'unica sequenza ordinata (nell'array A).La complessità del MergeSort la si ricava dalla seguente ricorrenza: T(n) = 2T(n/2) + theta(n) che ha soluzione theta(nlogn). Il theta(n) presente nella ricorrenza è il costo della procedura Merge su una   sequenza   di   elementi   di   dimensione   n.   Il   MergeSort,   dunque,   per   ordinare   un   array   di dimensione n, impiega un tempo pari a theta(nlogn); non ci sono casi pessimi o migliori.  

2.3 QuickSort

2.3.1 A doppia ricorsione (versione originale)

Il QuickSort è un algoritmo di ordinamento la cui complessità è quadratica nel caso pessimo, ma sia nel caso medio rappresenta una delle soluzioni migliori per effettuare l'ordinamento di un array in quanto, oltre ad essere veloce, è in­place.  

void QuickSort_A(int array[], int p, int r){ if (r - p > 1) { size_t q = Partition(array, p, r); QuickSort_A(array, p, q); QuickSort_A(array, q + 1, r); }}

int Partition(int array[], int p, int r)

{ int pivot, i, j; pivot = array[--r]; i = p - 1;

for (j = p; j <= r - 1; j++) { if (array[j] <= pivot) { ++i; Swap(&array[i], &array[j]); } }

Swap(&array[++i], &array[r]); return i;}

Anche QuickSort, come MergeSort, si basa sul paradigma divide et impera. Esso infatti è composto da due parti: 1) Utilizzando la procedura ausiliaria Partition, l'array A[p...r­1] viene partizionato nei due  sottoarray  A[p...q­1]  e  A[q+1...r­1]   (che  possono essere  vuoti),   tali   che  ogni  elemento  del sottoarray A[p...q­1] sia minore o uguale ad A[q] il quale a sua volta è minore o uguale a ogni elemento del sottoarray A[q+1...r­1]. 2) I due sottoarray A[p...q­1] e A[q+1...r­1] vengono ordinati chiamando ricorsivamente QuickSort. La procedura Partition seleziona l'ultimo elemento dell'array come pivot,   intorno al  quale verrà partizionato l'intero array. Il valore della variabile i rappresenta l'indice dell'ultimo elemento minore del pivot. Infatti, scorrendo l'array (per mezzo della variabile contatore j), non appena si trova un elemento minore del pivot, i viene aumentata di un'unità e viene fatto uno scambio tra A[i] e A[j]. La procedura termina quando j = r – 2. Solo a questo punto si ha lo scambio tra A[r­1] e A[i+1] e viene ritornato il valore i+1 (cioè la posizione ordinata del pivot).    Come già detto nell'introduzione al QuickSort, la complessità di questo algoritmo è O(n2 ) nel caso pessimo, ma nel caso medio e in quello migliore, ha una complessità pari ad O(nlogn). Il QuickSort rappresenta una delle soluzioni più rapide per ordinare un vettore di n elementi. Il caso pessimo infatti si ha solamente quando l'array di partenza è già ordinato in modo crescente o decrescente (in questo  caso  Partition  produce  un  sottoarray  con n  –  1  elementi   ed  uno  vuoto,  avendo  così   la seguente equazione di complessità: T(n) = T(n – 1) + theta(n) il cui valore è O(n2  ). Theta(n) è la complessità della procedura ausiliaria Partition.

2.3.2 A singola chiamata ricorsiva

Il QuickSort descritto precedentemente contiene due chiamate ricorsive a sé stesso, ma la seconda chiamata non è veramente necessaria. Qui sotto è riportato il codice del QuickSort che, sfruttando la 

ricorsione di coda, utilizza una sola chiamata ricorsiva.

void QuickSort_B(int array[], int p, int r){ while (r - p > 1) { int q = Partition(array, p, r); QuickSort_B(array, p, q); p = q + 1; }}

Questa  versione  del  QuickSort  usa una struttura  di  controllo   iterativa  (il  while)  al  posto dell'if presente   nella   versione   originale.   Solitamente   le   procedure   ricorsive   utilizzano   uno   stack   che contiene   le   informazioni   inerenti   ad   ogni   chiamata   ricorsiva,   compresi   i   valori   dei   parametri. Dunque, ogni volta che ci sarà una chiamata ricorsiva a QuickSort, verrà eseguito un push nello stack di tutte le informazioni relative a quella procedura (verranno inseriti nello stack i valori dei parametri  p ed r  e  il   return address,  cioè   l'indirizzo dell'istruzione successiva alla chiamata).  Il QuickSort   qui   esaminato   chiama   sé   stesso   fino   a   quando   non   dovrà   operare   su   un   array   di dimensione 1; successivamente, poiché non si entrerà nel ciclo while, p assumerà il valore di q + 1 (l'ultimo q prodotto da Partition inserito sullo stack). Alla fine, quando lo stack sarà interamente svuotato, l'array di partenza è ordinato.   

2.3.3 Iterativo

Un'ultima   variante   del   QuickSort   è   quella   iterativa.   Non   vengono   cioè   usate   le   due   chiamate ricorsive ma uno stack di supporto sul quale memorizzare gli intervalli da ordinare. 

void QuickSort_C(int array[], int p, int r){ typedef pair<int, int> Range;

Range rng(p, r); stack<Range> support; support.push(rng);

do { rng = support.top(); support.pop(); p = rng.first; r = rng.second;

while (r - p > 1) { int q = Partition(array, p, r);

if (r - q > 1) { rng.first = q + 1; rng.second = r;

support.push(rng); }

r = q; } } while (!support.empty());}

All'inizio viene definito un range costituito da una coppia di indici (first, second) rappresentante una sezione dell'array definita da [first, second) ed uno stack di supporto sul quale memorizzare le parti dell'array ancora da elaborare. Inizialmente viene fatto sullo stack il push (viene cioè inserito) del range (p, r), ovvero l'intero array. Poi, finchè lo stack non è vuoto, si entra in un loop che preleva (top() seguito da pop()) il primo elemento (di tipo range) dallo stack che contiene le informazioni circa i limiti dell'array da elaborare e finchè la dimensione dell'array stesso è maggiore di 1 viene chiamata   la   procedura   ausiliaria   Partition   che   memorizza   in   q   la   nuova   posizione   del   pivot. Successivamente, se r – q è maggiore di 1 viene assegnato al primo valore del range q + 1, mentre al secondo r; viene quindi fatto il push sullo stack del nuovo range che rappresenta il sottoarray destro. Infine viene dato ad r il valore di q. In questo modo viene ridotto il range sinistro a [p, q). Quando si uscirà dal ciclo while interno si preleverà il primo elemento dallo stack e verranno eseguiti gli stessi passi descritti precedentemente.   2.4 InsertionSort

InsertionSort è un semplice algoritmo di ordinamento basato sul confronto che ha il vantaggio di essere  in­place:  esso cioè  non utilizza memoria aggiuntiva,  ma esegue  l'ordinamento all'interno dell'array di partenza.

void InsertionSort(int array[], int p, int r){ int size = r - p; int item; for (int j = 1; j <= size - 1; j++) { item = array[j]; int i = j - 1;

while (i >= 0 && item < array[i]) { array[i + 1] = array[i]; i--; }

array[i + 1] = item; }}

InsertionSort  opera nel  modo seguente:  ogni  elemento A[j]  dell'array (con j    compreso tra  1  e size – 1), dopo essere stato memorizzato in una variabile temporanea (item nel nostro caso), viene confrontato con l'elemento che lo precede A[i], dove i = j – 1. Se item è maggiore o uguale di A[i], l'ordine degli elementi non viene modificato; se invece item è minore di A[i], quest'ultimo prenderà il posto di A[j]. Item verrà confrontato nuovamente con A[i – 1] il quale, se maggiore di item, verrà spostato in posizione A[i]. Questo procedimento prosegue finchè non si trova un elemento minore o uguale   ad   item   oppure   fino   a   quando   l'ultimo   elemento   confrontato   con   item   (A[0])   viene 

memorizzato   in  A[1]   (questo  significherebbe che   item,  alla   j­esima  iterazione,  è   il  più  piccolo elemento dell'array). L'algoritmo funziona correttamente in quanto conserva la seguente invariante di   ciclo:   all'   inizio   della     j­esima   iterazione   (con   j   compreso   tra   1   e   size   –   1)   il   sottoarray A[0 ... j – 1] è ordinato. InsertionSort termina quando j = size (esce dal ciclo for esterno) e a questo punto, per l'invariante di ciclo, abbiamo che il sottoarray A[0 ... size – 1] è ordinato; ma questo è proprio l'intero array. Otteniamo dunque che l'array A è ordinato. La complessità dell'InsertionSort nel caso peggiore e in quello medio è quadratica (O(n2), con n che indica la dimensione dell'input). Nel caso migliore, cioè quando l'array di partenza è già ordinato in modo crescente, impiega un tempo lineare (O(n)), poiché la guardia del ciclo while interno risulterà sempre falsa e le istruzioni al suo interno non verranno mai eseguite.  

2.5 Algoritmi misti

2.5.1 QuickSort + InsertionSort

Questo algoritmo misto sfrutta le prestazioni migliori di QuickSort e InsertionSort. Il primo, infatti, è molto efficiente nell'ordinare vettori di grandi dimensioni e disordinati; il secondo è un algoritmo veloce per array ordinati a blocchi (ricordiamo che un array è ordinato a blocchi di dimensione k quando ogni elemento del blocco t è  minore o uguale a ogni elemento del blocco t + 1, ma gli elementi di ogni blocco non sono necessariamente ordinati). 

void QuickInsSort(int array[], int p, int r){ QuickSort_K(array, p, r, Q_K); InsertionSort(array, p, r);}

void QuickSort_K(int array[], int p, int r, int k){ if (r - p > k) { size_t q = Partition(array, p, r); QuickSort_K(array, p, q, k); QuickSort_K(array, q + 1, r, k); }}

L'idea che sta alla base di questo algoritmo è  quella di utilizzare QuickSort per ordinare l'array disordinato fino ad avere un array ordinato a blocchi di una certa dimensione k. Per ottenere questo, basta una semplice modifica al codice del QuickSort originale: si cambia la condizione del primo if e, al posto di if (r – p > 1) si mette if (r – p > k). In questo modo il vettore sarà ordinato a blocchi di dimensione k (o minore di k) ciascuno. Successivamente, con un'unica passata di InsertionSort si ordina il vettore. La difficoltà maggiore consiste nel determinare il valore giusto di k. Se infatti k è troppo grande, si rischia di far lavorare troppo InsertionSort, aumentando così la complessità della “seconda   fase”   del   programma;   se   invece   k   è   troppo   piccolo,   l'algoritmo   avrebbe   prestazioni vicinissime al QuickSort originale. La procedura Partition utilizzata nel QuickInsSort è identica a quella del QuickSort. 

2.5.2 QuickSort + BubbleSort

Anche  questo  algoritmo  misto  combina   le  buone prestazioni  del  QuickSort   su  array  di  grandi 

dimensioni e quelle del BubbleSort su array di dimensioni minori. 

void QuickBubSort(int array[], int p, int r){ if (r - p > 1) { if (r - p < Q_K) BubbleSort(array, p, r); else { size_t q = Partition(array, p, r); QuickBubSort(array, p, q); QuickBubSort(array, q + 1, r); } }}

Il QuickBubSort, come l'algoritmo precedente, utilizza il QuickSort originale per ordinare a blocchi array di  grosse dimensioni.  A questo punto,   invece di  chiamare InsertionSort  che con un'unica passata ordina completamente il vettore, si  chiama BubbleSort su ogni blocco di dimensione k. Anche in questo caso bisogna stabilire sperimentalmente il valore di k che rende l'algoritmo il più efficiente   possibile.   K   non   dovrà   essere   troppo   grande   altrimenti   prevarrebbe   la   complessità quadratica del BubbleSort, ma nemmeno troppo piccolo, altrimenti le prestazioni assomiglierebbero molto a quelle del QuickSort originale. Si è sperimentato che buoni risultati vengono ottenuti con valori di k pari a 10.     

3.Metodologia e scelte implementative

Di   tutti   gli   algoritmi   di   ordinamento  descritti   ed   analizzati   fin'ora   si   vuole   calcolare   il   tempo d'esecuzione nel caso medio su array di dimensione n variabile (n = 10, 20, 50, 100, 200, 500, 1000, 2500, 5000) e con intervallo di confidenza del 95% per poter poi confrontare le loro prestazioni. Il primo problema che si verifica è  riuscire ad individuare il caso medio. Infatti, mentre il caso peggiore e quello migliore sono ben determinati (ad esempio nell'InsertionSort il caso migliore si ha quando  l'array  è  già  ordinato  in  partenza e  quello  peggiore  quando  l'array  è  ordinato   in  modo decrescente), il caso medio non è altrettanto ben definito. Esistono infatti dei casi (le istanze del problema) che non sono né quello migliore né quello peggiore. Tutte le istanze del problema dell'ordinamento di un vettore hanno la stessa probabilità di uscire. Dunque, se la dimensione del vettore da ordinare è n, esisteranno n! (il numero delle permutazioni) istanze, ognuna con probabilità  1/n!. Si può quindi supporre che i dati siano distribuiti in modo uniforme, ovvero che tutti siano identicamente probabili. Per questo motivo, per riempire l'array, è stato   utilizzato   un   generatore   di   numeri   casuali.   Nel   nostro   caso,   la   procedura    void LoadRandomArray(int array[], size_t size, long seed, int minVal, int maxVal), prende come argomenti l'array, la sua dimensione, il seme per il generatore di numeri casuali, i due valori minVal e maxVal, che costituiranno i limiti dell'intervallo al quale apparterranno i numeri prodotti   dalla   funzione  int GetNextRandom(int minVal, int maxVal).   Questa   procedura richiama  al   suo   interno   la   funzione  double GetNextRandom()  ,   la  quale   produce  un  numero casuale compreso nell'intervallo   [0,1),  per  poi   ritornare  al  chiamante un  numero   intero  casuale nell'intervallo [minVal, maxVal]. Al termine della procedura  LoadRandomArray avremo un vettore di   dimensione   size   riempito   con   numeri   casuali   (questo   rappresenta   una   singola   istanza   del problema). Per   calcolare   il   tempo  d'esecuzione  nel  caso  medio,   si  dovrebbero  valutare   i   tempi  di   tutte   le 

possibili istanze, sommarli, per poi dividerli per il numero delle istanze stesse (media aritmetica). Ma questo procedimento risulta pressochè impossibile, poiché solo per array di dimensioni pari a 10 si dovrebbero calcolare i tempi d'esecuzione dell'algoritmo di ordinamento su 10! = 3628800 istanze diverse! Ci si dovrà dunque aspettare una stima approssimata del tempo medio d'esecuzione, che d'ora in poi sarà chiamato E'[X(n)], calcolando i tempi non su tutte le possibili istanze del problema, bensì solo su un campione, costitituito da c << n! istanze (nel nostro caso c = 500). Logicamente, maggiore sarà la dimensione del campione, più il tempo medio approssimato E'[X(n)] si avvicinerà a quello reale E[X(n)].  La   procedura  double EvaluateSingleInstance(const int array[], size_t size,

SORT_ALGO algo)prende   come   argomenti   l'array   sul   quale   effettuare   l'ordinamento,   la   sua dimensione, l'algoritmo di ordinamento da utilizzare e ritorna il tempo di esecuzione dell'algoritmo stesso su un vettore di dimensione size (in seguito verranno descritti i passi per il calcolo del tempo d'esecuzione).Infine,   la  procedura  double EvaluateMultipleInstances(size_t size, SORT_ALGO algo, InfoAlgo *info) prende come argomenti la dimensione del vettore, l'algoritmo di ordinamento da utilizzare per ordinare l'array e il puntatore alla struttura info, sulla quale verranno caricati i seguenti dati: dimensione del vettore (size), il numero delle istanze (cn), il tempo medio (tm), il valore della varianza (var) e quello del delta (delta). La funzione appena descritta non fa altro che richiamare le procedure definite precedentemente (LoadRandomArray ed  EvaluateSingleInstance) tante volte quante sono il numero delle istanze (500) che costituiscono il campione. Il tempo d'esecuzione di ogni istanza viene memorizzato nella variabile t, mentre la variabile T tiene conto della somma dei tempi di ogni istanza. In questo modo è molto semplice calcolare il tempo medio E'[X(n)]: una volta usciti dal ciclo for basta dividere T per la dimensione del campione c.Ovviamente,   se   si   fosse   ripetuto   l'esperimento  con altri  valori,   si   sarebbe ottenuto  un   risultato leggermente divero da E'[X(n)], ma che comunque non si sarebbe discostato troppo dal valore della media  reale  E[X(n)].  Vi  sono  tuttavia  dei  casi  piuttosto  rari   in  cui   il   tempo medio E'[X(n)]  si discosta significativamente da quello reale (la loro percentuale la chiameremo k). Dunque, poiché nel nostro caso abbiamo un intervallo di confidenza del 95% (k = 0.05 = 5%), calcolando il tempo medio d'esecuzione E'[X(n)],  si  avrà   il  95% di probabilità  che tale valore disti  dal  valore reale E[X(n)] meno di delta (un parametro che verrà valutato in seguito). Quindi, calcolando il tempo medio E'[X(n)] su un campione di dimensione   c, si ottiene l'intervallo di confidenza all'  1 – k [E'[X(n)]   –   delta,   E'[X(n)]   +   delta]   il   cui   significato   generale   è   il   seguente:   se   si   ripetesse l'esperimento un grande numero di volte e per ognuna venisse calcolato l'intervallo di confidenza, solo il (k*100)% degli intervalli non conterrebbero il valore reale della media E[X(n)]. Nel codice sono riportate le formule per il calcolo del delta, il  quale a sua volta viene valutato usando   un   altro   parametro,   la   varianza   campionaria.   Tutti   questi   valori   statistici,   come   detto precedentemente,   sono  caricati  nella   struttura   info.  Queste  operazioni,  presenti   all'interno  della procedura   EvaluateMultipleInstances, vengono ripetute per ogni algoritmo eseguito su ogni vettore di dimensione n.Prima di descrtivere il procedimento per il calcolo del tempo d'esecuzione di un algoritmo, bisogna tenere presente un problema generale: quale deve essere la durata minima di un evento affinchè la si possa misurare con un orologio di precisione d con un errore dell'x% ? Innanzitutto, se misuriamo un tempo t con un orologio di precisione d, esso corrisponde ad un tempo effettivo che appartiene all'intervallo [t – d, t + d]. Il valore di t non dovrà essere circa uguale a d, altrimenti si potrebbe avere un errore del 100%. Una cosa è infatti avere un errore di d su un tempo t = 20d, un'altra è avere un errore di d su un tempo d'esecuzione t = d. Più in generale possiamo dire che se t = kd, l'errore di misurazione sarà  del (100/k)%. Dunque, se si vuole ottenere una misurazione con un errore dell'x% usando un orologio con risoluzione d, occore misurare un evento della durata di (100/x)d. Questa durata verrà in seguito chiamata tmin.

Ma come si fa a misurare il tempo d'esecuzione di un qualsiasi programma o di un generico evento? Basta utilizzare la funzione  clock()  offerta dalla libreria standard del C/C++ inclusa nell'header time.h. Questa funzione non prende nessun parametro e, dopo aver letto l'orologio di macchina (un registro  che  viene   incrementato  ogni  d   secondi),   restituisce  un  valore  di   tipo  clock_t.  Dunque, “interrogando” l'orologio di macchina attraverso clock() prima e dopo l'esecuzione dell'evento, è possibile calcolare il tempo d'esecuzione facendo una differenza tra i due valori. In questo modo si ottiene   un   valore   intero,   che   corrisponde   al   numero   di   battiti   trascorsi   dall'inizio   alla   fine dell'esecuzione. Se si vuole trasformare il numero di battiti in secondi, basterà dividere il risultato per la costante (anch'essa definita nel file time.h) CLOCKS_PER_SEC. Nel nostro caso abbiamo voluto calcolare i tempi d'esecuzione degli algoritmi con un errore del 5%. Per calcolare il tmin è stato prima necessario valutare la precisione di macchina d per mezzo della funzione double CalculatePrecision(), la quale non prende nessun argomento e restituisce il valore di d (il calcolatore utilizzato per la stima dei tempi ha precisione di macchina d = 0.01). Una volta che si conosce la durata minima che deve avere un programma (tmin appunto), per misurare le prestazioni   di   un   algoritmo   di   ordinamento   su   un   vettore   di   dimensione   n   basterà   ripetere l'algoritmo r volte fino a raggiungere il valore di tmin; naturalmente, al crescere di n, le ripetizioni dell'algoritmo   diminuiranno.   Inoltre,   poiché   l'algoritmo   verrà   ripetuto   r   volte,   bisogna   anche provvedere a fare una copia dell'intero array (operazione svolta dalla funzionevoid CopyArray(int copy_array[], const int array[], size_t size), che prende come argomenti il vettore copy_array, sul quale viene copiato il vettore array di dimensione size), affinchè l'algoritmo venga ripetuto sullo stesso identico array e non sull' array già ordinato precedentemente.La funzione  size_t GetRepetition_Lordo(SORT_ALGO algo, const int array[], size_t n) prende come argomenti l'algoritmo di ordinamento, l'array su cui esso opera e la dimensione n dell'array stesso. Questa procedura fa prima una stima approssimativa del numero delle ripetizioni dell'algoritmo e della funzione CopyArray affinchè impieghino un tempo maggiore o uguale a tmin per poi “raffinarla” sempre di più attraverso il metodo della bisezione. Il massimo errore in questa stima è di 5 (numero che si può stabilire arbitrariamente). La procedura ritornerà dunque il numero delle ripetizioni dell'algoritmo di ordinamento più la procedura per la copia del vettore. La   funzione  size_t GetRepetition_Tara(const int array[], size_t n)  prende   come argomenti   un   array   e   la   sua   dimensione   n   e,   utilizzando   lo   stesso   metodo   della   procedura precedentemente descritta, ritorna il numero delle ripetizioni della sola funzione CopyArray. La   procedura  EvaluateSingleInstance,   dunque,   per   calcolare   il   tempo   d'esecuzione   di   un algoritmo di ordinamento su un vettore di dimensione n, non fa altro che ripetere con un ciclo for r volte   (r  è   il   risultato   della   procedura  GetRepetition_Lordo)   l'algoritmo  più   il    CopyArray  e dividere poi per r il tempo d'esecuzione. In questo modo si ottiene una stima del tempo lordo, cioè quanto tempo impega l'algoritmo per ordinare  l'array,  sommato al   tempo per  la copia dell'array stesso. Per calcolare il tempo effettivo del solo algoritmo di ordinamento si dovrà sottrarre il tempo per la copia dell'array. Quindi si utilizza nuovamente un ciclo for che farà ripetere r' volte (r' è il risultato   della   procedura    GetRepetition_Tara)   il  CopyArray  per   poi   dividere   il   tempo d'esecuzione per r'. Si ottiene così il valore della tara, cioè il tempo d'esecuzione della procedura CopyArray.   Il   tempo in  secondi  del  solo algoritmo di  ordinamento è  dato da (tlordo – ttara)   / CLOCKS_PER_SEC.  

    

    4.Risultati ottenuti, confronti e conclusioni

Di seguito sono riportati i risultati ottenuti sperimentalmente e i grafici di tutti gli algoritmi sin qui descritti   ed   analizzati.   Successivamente   verranno   confrontate   le   prestazioni   di   alcuni   di   essi. Saranno inoltre riportate solo la dimensione n del vettore su cui opera l'algoritmo e il tempo medio d'esecuzione;   se   si   vogliono   consultare   i   valori   della   varianza,   del   delta   e   dell'intervallo   di confidenza è possibile farlo aprendo i file relativi ai vari algoritmi all'interno della cartella Analysis.

dimensione istanze tempo medio10 500 0.00000015620 500 0.00000293050 500 0.000007625100 500 0.000091236200 500 0.000494354500 500 0.0023200001000 500 0.0103535442500 500 0.0643773805000 500 0.255419180

dimensione istanze tempo medio10 500 0.00000034620 500 0.00000677250 500 0.000006912

100 500 0.000068962200 500 0.000156997500 500 0.0002289911000 500 0.0002182882500 500 0.0010878405000 500 0.002639565

dimensione istanze tempo medio10 500 0.00000042020 500 0.00000078350 500 0.000010360100 500 0.000029663200 500 0.000070388500 500 0.0001574571000 500 0.0002223842500 500 0.0004138735000 500 0.001412933

dimensione istanze tempo medio10 500 0.00000047220 500 0.00000101550 500 0.000010006100 500 0.000030733200 500 0.000065080500 500 0.000152043

1000 500 0.0001830612500 500 0.0003326995000 500 0.001240178

dimensione istanze tempo medio10 500 0.00000093520 500 0.00000109450 500 0.000001457100 500 0.000009691200 500 0.000045738500 500 0.0001569071000 500 0.0002563522500 500 0.0005377215000 500 0.000952928

dimensione istanze tempo medio10 500 0.00000039020 500 0.00000214250 500 0.000008014100 500 0.000080499200 500 0.000440459500 500 0.0023749791000 500 0.0099842842500 500 0.0633441075000 500 0.250941742

dimensione istanze tempo medio10 500 0.00000073320 500 0.00000098450 500 0.000006445100 500 0.000022264200 500 0.000035620500 500 0.0001157991000 500 0.0001250382500 500 0.0001823895000 500 0.000900694

dimensione istanze tempo medio10 500 0.00000028420 500 0.00000133550 500 0.000005888100 500 0.000007807200 500 0.000126364500 500 0.0001507051000 500 0.0020902142500 500 0.0175409635000 500 0.064697567

dimensione istanze tempo medio10 500 0.00000021220 500 0.00000129850 500 0.000002944100 500 0.000017455200 500 0.000031317500 500 0.0001197121000 500 0.0001338312500 500 0.0001833135000 500 0.000937565

Dalle tabelle ed i grafici riassuntivi sul comportamento degli algoritmi di ordinamento analizzati si possono fare alcune interessanti considerazioni.

1. Benché gli algoritmi InsertionSort e BubbleSort abbiano complessità quadratica, essi si rivelano molto efficienti su array di piccole dimensioni (non superiore a 10 o al massimo 15). Su questo tipo di vettori le loro prestazioni sono migliori rispetto ad algoritmi che hanno complessità pari ad O(nlogn) nel caso medio come il MergeSort o il QuickSort. 

2.  Per ordinare array di grosse dimensioni (senz’altro maggiori di 15) gli algoritmi più efficienti risultano essere il QuickBubSort e il QuickInsSort, che sfruttano le caratteristiche del QuickSort di   operare   velocemente   su   vettori   di   grandi   dimensioni   e   quelle   ottime   del   BubbleSort   (o InsertionSort)  di ordinare rapidamente array molto piccoli. 

3.  Il BubbleSort ottimizzato è leggermente migliore rispetto a quello originale su ogni dimensione dell’array.  Questo   fa   capire   i   limiti  del  BubbleSort   il   quale,   anche   se   ottimizzato,   resta  un algoritmo piuttosto inefficiente. 

4. Il  QuickSort  originale,  pur  essendo uno degli  algoritmi  più  efficienti,  può  essere  migliorato ulteriormente.  Nel   complesso   si   sono   riscontrate   prestazioni  migliori   oltre   che  da  parte   del QuickInsSort e QuickBubSort anche da parte del QuickSort a singola chiamata ricorsiva e del QuickSort iterativo.

5. Tra   InsertionSort   e   BubbleSort,   sebbene   abbiano   entrambe   nel   caso   medio   complessità quadratica, il primo risulta sensibilmente migliore del secondo. Questo significa che le costanti moltiplicative del InsertionSort sono inferiori. 

6. Per concludere, i due migliori algoritmi per l’ordinamento risultano essere il QuickInsSort ed il QuickBubSort   i   quali  hanno  prestazioni  molto   simili.   Inoltre   sono   totalmente   in­place:   non utilizzano memoria aggiuntiva. Questa si rivela essere l’unica pecca di algoritmi molto efficienti in termini di tempo come il QuickSort iterativo che utilizza uno stack di supporto e il MergeSort, che fa continuamente uso di due vettori ausiliari per portare a termine l’ordinamento.