/*
Definisce un array, inizializzandolo per agevolare le prove

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


import javax.swing.JOptionPane;

public class QuickSortAnimato
{
	static int sp=3;
	static int n=26;

	public static int partiziona(int[] v, int from, int to)
	{
		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 è maggiore di j
			while(i<j && v[j]>=separatore)
				j--;
// ora j indica un valore minore di separatore
// oppure è minore o uguale a i
			if(i<j)
			{
				int app=v[i];
				v[i]=v[j];
				v[j]=app;
			}
		}
		if(v[i]>separatore)
		{
			i--;
		}
		int app=v[i];
		v[i]=v[from];
		v[from]=app;
		return i;
	}


	public static void quick(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);
stampaZona(from, separazione, to);
stampaArray(v, from, to);
			quick(v, from, separazione-1);
			quick(v, separazione+1, to);
		}
	}
	
	
	public static void quickSort(int[] v)
	{
		quick(v, 0, v.length-1);
	}
		
    
    public static int[] leggiArrayInt()
    {
//		int[] a={5,sp,7,8,210,3sp,6sp,2,3,5sp,6};

		int[] a=new int[26];
		for(int i=0; i<a.length; i++)
			a[i] = (int)(Math.random()*100);
// evitiamo la lettura per testare piu' agevolmente il codice

//        int n=Integer.parseInt(JOptionPane.showInputDialog("Dimensione dell'array?"));
//        int[] a = new int[n];
//        for(int i=0; i<a.length; i++)
//            a[i]=Integer.parseInt(JOptionPane.showInputDialog("digita elemento ["+i+"]"));

        return a;
    }


	private static void stampaZona(int from, int x, int to)
	{
		System.out.println();
		int i=0;
		while(i<sp*x)
		{
			System.out.print(" ");
			i++;
		}
		while(i<sp*(x+1))
		{
			System.out.print("*");
			i++;
		}
		System.out.println();
	}


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


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


    public static void main(String[] x)
    {
        int[] vettore;
        vettore=leggiArrayInt();
        System.out.println("prima dell'ordinamento");
        stampaArray(vettore, 0, vettore.length-1);
        
        quickSort(vettore);
        
        System.out.println("dopo l'ordinamento");
        stampaArray(vettore, 0, vettore.length-1);

        System.exit(0);
	}
}