/*
 Il metodo selection dato un array non ordinato "v" e un intero "rank", restituisce
 il "rank"-esimo minimo, cioe' l'elemento dell'array che occuperebbe la posizione
 "rank" qualora l'array venisse ordinato.
 Il problema potrebbe essere risolto ordinando l'array, ma l'algoritmo qui
 proposto permette di risolvere il problema con una complessita' computazionale
 attesa inferiore, in quanto il tempo atteso e' O(n) invece dell'O(n log n)
 necessario a ordinare l'array.
 
 L'algoritmo utilizza lo stesso approccio del Quick Sort.
 Viene chiamato il metodo partiziona, identico a quello utilizzato dal Quick
 Sort, e in base alla posizione restituita si continua la ricerca del k-esimo
 elemento su una sola delle due porzioni. L'algoritmo termina nel caso in cui il
 metodo partiziona restituisca esattamente la posizione k.
 
 La versione implementata in questa classe mostra graficamente il comportamento dell'algoritmo. Notare che l'array non viene ordinato completamente.
*/		

import javax.swing.JOptionPane;

public class SelectionAnimato {
	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"));
		int elemento = selection(vettore, x);
		
		System.out.println("l'elemento di rank "+x+" e' "+elemento);
		printlnArray(vettore);

		System.exit(0);
	}

	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
		return quickSelection(v, 0, v.length-1, rank);
	}		

	public static int 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 v[rank];
		else {
			int separazione=partiziona(v, from, to);
// l'istruzione successiva serve esclusivamente a mostrare graficamente il funzionamento dell'algoritmo
			printlnArray(v, separazione);
			
			if(separazione==rank)
				return v[rank];
			else if(separazione > rank) {
// l'istruzione successiva serve esclusivamente a mostrare graficamente il funzionamento dell'algoritmo
				printlnArray(v, from, separazione-1);
				return quickSelection(v, from, separazione-1, rank);
			}
			else {
// l'istruzione successiva serve esclusivamente a mostrare il funzionamento dell'algoritmo
				printlnArray(v, separazione+1, to);
				return quickSelection(v, separazione+1, to, rank);
			}
		}
	}

	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 scambia(int[] v, int pos1, int pos2) {
		int app = v[pos1];
		v[pos1] = v[pos2];
		v[pos2] = app;
	}
	
	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
	static int sp=3;
	
	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);
	}
}