next up previous contents
Next: Fibonacci con memoization Up: Esercizi svolti (Thread) Previous: Ricerca di un elemento   Indice

Quicksort

Si realizzi un programma che effettua l'ordinamento di un vettore di interi secondo il metodo del quicksort. Il vettore di interi sia generato utilizzando un generatore di numeri pseudocasuali. L'ordinamento sia realizzato in modo che ogni chiamata ricorsiva del quicksort corrisponda all'attivazione di un thread indipendente.

Vediamo come possiamo realizzare la classe Quicksort, ovvero come possiamo definire il thread che ordina (porzioni di) vettori secondo il metodo del quicksort. Il codice potrebbe essere il seguente:

public class QuickSort extends Thread {

    private int[] vector;
    private int p,r;
    private Massimo max;

    QuickSort(int [] v, int p, int r, Massimo m) {
        // inizializzazione dei parametri
        this.vector = v;
        this.p = p;
        this.r = r;
        this.max = m;
    }

    public void run() {
        // ordinamento del vettore
        // prima il partizionamento
        max.max(this.activeCount());
        if(p<r) {
            int pivot_i = Partition(vector,p,r);
            Thread primaparte =null, secondaparte=null;
                primaparte = new QuickSort(vector,p,pivot_i,max);
                secondaparte = new QuickSort(vector,(pivot_i+1),r,max);
                primaparte.start();
                secondaparte.start();
            try {
                    primaparte.join();
                    secondaparte.join();
            } catch (InterruptedException e) {}
        }
        return;
    }
    
    private int Partition(int[] vector, int p, int r) 
    {
        int pivot = vector[p];
        int i = (p-1);
        int j = (r+1);
        while(true) {
            do {
                j = j - 1; 
            } while(vector[j]>pivot);
            do {
                i = i + 1; 
            } while(vector[i]<pivot);
            if(i<j) {
                int temp = vector[i];
                vector[i] = vector[j];
                vector[j] = temp;
            } else {
                return(j);
            }
        }
    }

}
La procedura Partition serve solo a dividire il vettore in due parti, contenenti numeri piu' piccoli e piu' grandi del pivot, rispettivamente. Il parametro Massimo max serve per contare il massimo numero di thread attivi, e non va considerato ai fini della comprensione dell'algoritmo. Ogni volta che attiviamo il thread, questo provvede a procurasi il pivot e a dividere il vettore in due. A questo punto attiva due nuovi thread per ordinare i due (semi)vettori. Alla terminazione dei due thread restituisce il controllo al chiamante.

Notare che non vengono ricopiati i vettori ordinati nel vettore risultato. Poiche' i vettori sono di fatto passati per riferimento si effettua l'ordinamento "sul posto". Possiamo farlo senza problemi perche' i due thread generati lavorano su parti diverse del vettore, opportunamente divise dalla Partition.

Avendo a disposizione questo codice, e la classe Massimo:

public class Massimo {
    int max;

    Massimo() {
        max = 0;
    }

    public synchronized void max(int n) {
        if(n>max) 
            max = n;
    }

    public synchronized int get() {
        return(max);
    }
}
che serve unicamente per contare i thread attivi (ovvero per tener conto del massimo numero di thread attivi), possiamo scriverci il main come segue:
import java.util.Random;

public class Main {

    public static void main (String[] args) {
        // parse degli argomenti della riga di comando e/o assegnamento
        // dei valori di default
        // lunghezza del vettore da ordinare
        int n;
        final int MAX = 1000;
        try {
            n = Integer.parseInt(args[0]);
        } catch (Exception e) {
            n = 10;
        }
        int[] v = new int[n];
        // inizializzazione del vettore con numeri random
        Random generatore = new Random();
        for(int i=0;i<n;i++) 
            v[i] = generatore.nextInt(MAX);
        // stampa del vettore per controllo inizio
        for(int i=0;i<n;i++) 
            System.out.print(v[i]+" ");
        System.out.println("");
        // inizio dell'ordinamento: creazione del primo thread, 
        // e' quello che ordina tutto il vettore
        Massimo max = new Massimo();

        Thread qs = new QuickSort(v,0,n-1,max);
        qs.start();
        // attesa della fine dell'ordinamento
        try {
            qs.join();
        } catch(InterruptedException e) {}
        // stampa del vettore finale per controllo
        for(int i=0;i<n;i++) 
            System.out.print(v[i]+" ");
        System.out.println("");
        // stampa il numero massimo di thread attivi contemporaneamente
        System.out.println("Numero massimo di thread attivi contemporaneamente = "+
                           max.get());
        return;
    }
}
L'esecuzione del programma su vettori di varia dimensione porta ai risultati che ci aspettiamo:
DispensaThread/Quicksort> java Main 10
442 725 898 258 904 636 916 744 371 284
258 284 371 442 636 725 744 898 904 916
Numero massimo di thread attivi contemporaneamente = 13
DispensaThread/Quicksort> java Main 50
738 172 404 358 185 482 713 549 285 171 742 15 593 165 275 242 168 674 138 ....
6 15 22 69 77 89 117 138 165 168 171 172 174 185 242 245 269 275 285 312 317 ...
Numero massimo di thread attivi contemporaneamente = 34
DispensaThread/Quicksort> java Main 100
761 621 36 228 791 128 587 715 724 32 602 842 113 85 269 97 129 122 247 44 318 ...
0 7 18 29 32 36 36 44 47 47 85 97 98 106 113 122 128 129 143 149 158 172 178 ...
Numero massimo di thread attivi contemporaneamente = 84
DispensaThread/Quicksort>


next up previous contents
Next: Fibonacci con memoization Up: Esercizi svolti (Thread) Previous: Ricerca di un elemento   Indice
Danelutto Marco 2002-11-15