/*
 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. Ad esempio, se il valore del parametro rank
 fosse pari alla meta' della lunghezza dell'array il metodo restituirebbe il mediano
 degli elementi presenti nell'array.

 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.
*/		

import javax.swing.JOptionPane;
import java.util.Arrays;

public class Selection {
	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);

		System.exit(0);
	}

	public static int selection(int[] v, int rank) {
/* NON DOVREI MODIFICARE L'ARRAY, visto che il metodo deve eseguire una ricerca!!!
 * sarebbe meglio copiarlo in un altro
 * array, e restituire l'int con il rank voluto invece di void
 */
 		int[] nuovoArray = Arrays.copyOf(v, v.length);
		return quickSelection(nuovoArray, 0, nuovoArray.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) {
			int separazione=partiziona(v, from, to);
			
			if(separazione==rank)
				return v[rank];
			else if(separazione > rank) {
				return quickSelection(v, from, separazione-1, rank);
			}
			else {
				return quickSelection(v, separazione+1, to, rank);
			}		
		}
		else {
			return v[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;
	}

	public static void printlnArray(int[] v) {
		int i;
		for(i=0; i<v.length; i++)
			System.out.print(" "+v[i]);
		System.out.println();
	}
}