QuickSort

Questa lezione ha come oggetto l'algoritmo di ordinamento QuickSort.

1. Leggere lo pseudocodice seguente:

   Partition(A,p,r)
   x = A[r]
   i = p-1
   FOR (j=p to r-1)
     IF (A[j] <= x)
       i = i + 1
       Exchange(A, i, j)
     ENDIF
   ENDFOR
   Exchange(A, i+1, r)
   return i+1
   
   QuickSort(A,p,r)
   IF (p < r)
        q = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)
   ENDIF
   

2. Scrivere una classe QuickSort che ordina, in senso crescente, un vettore casuale di interi con il metodo do ordinamento QuickSort.
3. Scrivere una classe SortWorkBench che confronta i tempi degli algoritmi di ordinamento finora studiati usando la seguente metodologia:
   1. definire una sequenza dimensionale del problema dell'ordinamento con valori crescenti, ad esempio (10, 100, 1000, 10000, ...), oppure (10, 20, 50, 100, 200, 500, 1000, 2000, 5000, ...);
   2. per ogni dimensione, generare un campione di vettori casuali di quella dimensione (in prima istanza fissare la grandezza del campione ad una costante indipendentemente dalla dimensione dei dati);
   3. per ogni campione generato, eseguire ogni algoritmo di ordinamente su tutti i vettori del campione, prendere i tempi delle singole esecuzioni, e calcolare la media, la deviazione standard, e il coefficiente di variazione (deviazione fratto media);
   4. confrontare le medie ottenute per i diversi algoritmi.
   
   
   Usare il seguente codice per prendere il tempo agli algoritmi:

   timeStart = System.currentTimeMillis();
   // do something
   timeEnd = System.currentTimeMillis();
   time = timeEnd - timeStart;
   

   Significativitą del campione

   E' possibile determinare la dimensione del campione in modo tale che l'errore statistico commesso sia inferiore ad una certa soglia. L'intervallo di confidenza per la media nel caso di distribuzione normale dei tempi con varianza incognita risulta:

   $\displaystyle{[\hat{\mu} - t_{(n-1, \alpha/2)} \frac{\hat{s}}{\sqrt{n}}, \hat{\mu} + t_{(n-1, \alpha/2)} \frac{\hat{s}}{\sqrt{n}}]$

   dove:

   1. $n$ č la dimensione del campione;
   2. $\hat{\mu} = \frac{1}{n} \sum_i x_i$ č la media campionaria;
   3. $\hat{s} = \sqrt{\frac{1}{n} \sum_i (x_i - \hat{\mu})^2}$ č la deviazione standard campionaria;
   4. $1 - \alpha$ č il livello di confidenza. Tipicamente $\alpha$ assume i valori 0.1, 0.05, 0.01;
   5. $t_{(n-1, \alpha/2)$ č il valore che determina un intervallo centrato nell'origine con area sottesa alla curva pari a $1 - \alpha$ per la $t$ di student con $n-1$ gradi di libertą (comando qt($1 - \alpha /2$, n-1) in R, circa 1.96)

   Se definiamo l'errore assoluto:

   $\displaystyle{\epsilon_\alpha = t_{(n-1, \alpha/2)} \frac{\hat{s}}{\sqrt{n}}$

   allora l'errore relativo risulta pari a $\frac{\epsilon_\alpha}{\hat{\mu}}$. La tecnica consiste nell'aggiungere nuovi elementi al campione finchč l'errore relativo diventa minore di una certa soglia fissata (ad esempio 0.05).