import java.util.Random;

class QuicksortProg{
    public static void main(String[] args){
        int len = Integer.parseInt(args[0]);
        int [] tid = new int[11];
        for(int i = 0; i < 11; i++){
            int[] arr = new int[len];
            Random r = new Random();
            for(int j = 0; j < arr.length; j++){
                arr[j] = r.nextInt(len-1);
            }
            long start = System.nanoTime();
            int[] k = new QuicksortCalc().quicksort(arr,0,arr.length-1);
            double  timeTakenNS = (System.nanoTime() - start)/1000000.0;
            tid[i] = (int)timeTakenNS;
            System.out.println(timeTakenNS);
        }
        tid = QuicksortCalc.insertSort(tid,0,10);
        System.out.println("Median sorteringstid for 11 gjennomlop:"+tid[5]+"ms. for n="+len);
    }
}

class QuicksortCalc{
    int INSERT_LIM = 48;

    /*FUNC*/
    int[] quicksort(int[] array, int left, int right){
        if (right-left < INSERT_LIM){
            return insertSort(array,left,right);
        }else{
            int pivotValue = array[(left + right) / 2];
            swap(array, (left + right) / 2, right);
            int index = left;

            for (int i = left; i < right; i++) {
                if (array[i] <= pivotValue) {
                    swap(array, i, index);
                    index++;
                }
            }
            swap(array, index, right);
            int index2 = index;
            while(index2 > left && array[index2] == pivotValue){
                index2--;
            }

            /*REC*/
            array = quicksort(array, left,  index2);
            /*REC*/
            array = quicksort(array, index + 1, right);
            return array;
        }
    }


    static int[] insertSort(int a[],int left, int right){
        if (left < right){
            int i,k,t;

            for (k = left+1; k <= right; k++){
                t = a[k] ;
                i = k;

                while ( a[i-1]  > t ){
                    a[i] = a[i-1];
                    if (--i == left) break;
                }
                a[i] = t;
            }
        }
        return a;
    }


    void swap(int[] array, int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}