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>