/*
Ordina un'array con l'algoritmo quick sort

L'algoritmo e' descritto nel testo di Cormen, Leiserson, Rivest,
Introduzione agli algoritmi
Jackson Libri
Volume 1, Capitolo 8 (fino a 8.3 compreso) pagg.145-153
*/		

import javax.swing.JOptionPane;

public class QuickSort {
	static int sp=3;
	
	public static void scambia(int[] v, int pos1, int pos2) {
		int app = v[pos1];
		v[pos1] = v[pos2];
		v[pos2] = app;
	}
	
	public static int partiziona(int[] v, int from, int to) {
		// le due righe seguenti realizzano la scelta random del separatore
		int sceltaSeparatore = from + (int)(Math.random()*(to-from+1));
		scambia(v, sceltaSeparatore, from);
		
		int separatore = v[from];
		int i = from+1;
		int j = to;
		while(i<j) {
			while(i<j && v[i]<=separatore)
				i++;
			// ora i indica un valore maggiore di separatore
			// oppure i e' maggiore di j
			while(i<j && v[j]>=separatore)
				j--;
			// ora j indica un valore minore di separatore
			// oppure i e' maggiore di j
			if(i<j)
				scambia(v, i, j);
		}
		if(v[i]>separatore)
			i--;
		// posiziona correttamente il separatore
		scambia(v, i, from);
		return i;
	}

	public static void quickSort(int[] v, int from, int to) {
		// ordina l'intervallo da from a to, estremi inclusi
		if(from>=to)
			return;
		else {
			int separazione=partiziona(v, from, to);
			// le chiamate a printlnArray servono solo a mostrare graficamente il funzionamento dell'algoritmo
			printlnArray(v, separazione);
			printlnArrayPivot(v, from, separazione, to);
			
			quickSort(v, from, separazione-1);
			quickSort(v, separazione+1, to);
		}
	}
	
	public static void sort(int[] v) {
		quickSort(v, 0, v.length-1);
	}		



    public static int[] randomArray() {
		int[] a=new int[26];
		for(int i=0; i<a.length; i++)
			a[i] = (int)(Math.random()*100);
        return a;
    }

// i metodi seguenti servono solo a mostrare graficamente il comportamento dell'algoritmo
	private static String completaConSpazi(int x) {
		String s=""+x;
		int numSpazi=sp-s.length();   // sp vale p.es. 5
		for(int i=0; i<numSpazi; i++)
			s=" "+s;
		return s;
	}

	private static String completaConSpazi(String x) {
		String s=""+x;
		int numSpazi=sp-s.length();   // sp vale p.es. 5
		for(int i=0; i<numSpazi; i++)
			s=" "+s;
		return s;
	}

    public static void printlnArray(int[] v, int pos) {
		int i;
		for(i=0; i<sp*pos; i++)
			System.out.print(" ");
		System.out.print(completaConSpazi(v[pos]));
		System.out.println(" pivot");
    }

    public static void printlnArray(int[] v, int from, int to) {
		int i;
		for(i=0; i<sp*from; i++)
			System.out.print(" ");
        for(i=from; i<=to; i++)
            System.out.print(completaConSpazi(v[i]));
		System.out.println();
    }

    public static void printlnArrayPivot(int[] v, int from, int sep, int to) {
		int i;
		for(i=0; i<sp*from; i++)
			System.out.print(" ");
        for(i=from; i<sep; i++)
            System.out.print(completaConSpazi(v[i]));
		System.out.print(completaConSpazi(""));
        for(i=sep+1; i<=to; i++)
            System.out.print(completaConSpazi(v[i]));
		System.out.println();
    }

    public static void printlnArray(int[] v) {
		printlnArray(v, 0, v.length-1);
	}
	
    public static void main(String[] x)
    {
        int[] vettore;
        vettore=randomArray();
		
        System.out.println("prima dell'ordinamento");
        printlnArray(vettore);
        
        sort(vettore);
        
        System.out.println("dopo l'ordinamento");
        printlnArray(vettore);

        System.exit(0);
	}
}