/*
*/		

import javax.swing.JOptionPane;

public class Selection {
	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 quickSelection(int[] v, int from, int to, int rank) {
		// posiziona correttamente l'elemento con rank richiesto. Si assume che from <= rank <= to
		if(from>=to)
			return;
		else {
			int separazione=partiziona(v, from, to);
			printlnArray(v, separazione);
			
			if(separazione==rank)
				return;
			else if(separazione > rank) {
				printlnArray(v, from, separazione-1);
				quickSelection(v, from, separazione-1, rank);
			}
			else {
				printlnArray(v, separazione+1, to);
				quickSelection(v, separazione+1, to, rank);
			}
		}
	}
	
	public static int selection(int[] v, int rank) {
// NON DOVREI MODIFICARE L'ARRAY!!! meglio copiarlo in un altro
// array, e restituire l'int con il rank voluto invece di void
		quickSelection(v, 0, v.length-1, rank);
	}		



    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;
	}

    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 printlnArray(int[] v) {
		printlnArray(v, 0, v.length-1);
	}
	
    public static void main(String[] args)
    {
        int[] vettore;
        vettore=randomArray();
		
        System.out.println("array random:");
        printlnArray(vettore);
        
		int x = Integer.parseInt(JOptionPane.showInputDialog("digita il rank dell'elemento da cercare"));
        selection(vettore, x);
        
        System.out.println("l'elemento di rank "+x+" e' "+vettore[x]);
        printlnArray(vettore);

        System.exit(0);
	}
}