import java.util.*;

interface Finder
{
    public int find(int[] list, int index);
}

class EasyFinder implements Finder
{
    public int find(int[] list, int index)
    {
        Arrays.sort(list);
        return list[index];
    }
}

class FastFinder implements Finder
{
    public int find(int[] list, int index)
    {
        return findHelper(list,index,0,list.length-1);
    }

    private void swap(int[] list, int a, int b)
    {
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
    
    private int findHelper(int[] list, int index,
                           int first, int last)
    {
        int lastIndex = first;
        int pivot = list[first];
        for(int k=first+1; k <= last; k++){
            if (list[k] <= pivot){
                lastIndex++;
                swap(list,lastIndex,k);
            }
        }
        swap(list,lastIndex,first);
        
        if (lastIndex == index)
            return list[lastIndex];
        if (index < lastIndex )
            return findHelper(list,index,first,lastIndex-1);
        else
            return findHelper(list,index,lastIndex+1,last);     
    }
}

public class FindKth
{

    static double stress(int[] list, Finder finder, int trials)
    {

        int[] copy = new int[list.length];
        Random rando = new Random();
        double start = System.currentTimeMillis();
        for(int k = 0; k < trials; k++){
            System.arraycopy(list,0,copy,0,list.length);
            int index = rando.nextInt(list.length);
            
            int f = finder.find(copy,index);
            
            if (f != index){
                System.out.println("failed on "+index+" with "+f);
            }
        }
        double stop = System.currentTimeMillis();
        return (stop-start)/1000.0;
    }

    public static void main(String[] args)
    {
        final int SIZE = 200000;
        final int TRIALS = 10;
        ArrayList alist = new ArrayList();
        int [] list = new int[SIZE];
        for(int k=0; k < SIZE; k++){
            alist.add(new Integer(k));
        }
        Collections.shuffle(alist);
        for(int k=0; k < SIZE; k++){
            list[k] = ((Integer) alist.get(k)).intValue();
        }

        Finder easyfinder = new EasyFinder();
        Finder fastfinder = new FastFinder();

        double etime = stress(list, easyfinder,TRIALS);
        double ftime = stress(list, fastfinder,TRIALS);
        System.out.println("easy time = "+etime);
        System.out.println("fast time = "+ftime);       
    }
}