codice:
/* 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. */
import javax.swing.JOptionPane;
public class Selection
{
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);
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);
}
}
}
public static int partiziona(int[] v, int from, int to)
{
// le due righe seguenti realizzano la scelta random del separatore
int sceltaSeparatore = (from+to)/2;
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;
}*/ //Lo messo io come commento per fare una cosa più semplice
public static void printlnArray(int[] v)
{
int i;
for(i=0; i<v.length; i++)
System.out.print(" "+v[i]);
System.out.println();
}
public static void main(String[] args)
{
int[] vettore={1, 30, 55, 2, 0, 66, 34, 100, 10, 12, 13, 11}; //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);
}
}
Alcune cose già c'erano di commenti prima il programma creare una sequenza random io ho messo dei valori fissi per capire meglio di cosa si trattava ma ugualmente non ci riesco 
