import java.util.*;
public class verkefni1 {

	public static void main( String[] args ){
		Random rng = new Random();
		long avgASpeed = 0;
		long avgBSpeed = 0;
		long avgCSpeed = 0;
		int myK = 0;
		long startTime;
		long endTime;
		long[] myAverageTimes = new long[200];
		int ktimes = 10; //How many times for average
		int h = 20000; //Number of integers
		double[] A = new double[h]; //Random numbers from 0 to A.length.
		double[] B = new double[h]; //0 sqrt(n) times, 1 sqrt(n) times, ... sqrt(n) sqrt(n) times.
		double[] C = new double[h]; //Almost ordered array.

//		MEÐALTAL MARGRA TILRAUNA.
//		for(myK = 0; myK<200; myK++){
//			for(int g = 0; g<ktimes; g++){
//				//Making A
//				for(int i = 0; i<A.length; i++){
//					A[i] = i;
//				}
//				shuffleArray(A);
//
//				//A
//				long startTime = System.nanoTime();
//				QuickSort(A, 0, A.length-1, myK);
//				long endTime = System.nanoTime();
//				avgASpeed += (endTime - startTime);
//
//			}
//			avgASpeed = avgASpeed / ktimes;
//			myAverageTimes[myK] = avgASpeed;
//			avgASpeed = 0;
//		}
//		for(int i = 0; i<200; i++){
//			System.out.print(myAverageTimes[i]+", ");
//		}
//		for(myK = 0; myK<200; myK++){
//			for(int g = 0; g<ktimes; g++){
//				//Making B
//				int innerk = 0;
//				int innern = 1;
//				for(int i = 0; i<B.length; i++){
//					if(i>=innern*Math.sqrt(B.length)){
//						innern++;
//						innerk++;
//					}
//					B[i] = innerk;
//				}
//				shuffleArray(B);
//				//B
//				startTime = System.nanoTime();
//				QuickSort(B, 0, B.length-1, myK);
//				endTime = System.nanoTime();
//				avgBSpeed += (endTime - startTime);
//			}
//			avgBSpeed = avgBSpeed / ktimes;
//			myAverageTimes[myK] = avgBSpeed;
//			avgBSpeed = 0;
//		}
//		for(int i = 0; i<200; i++){
//			System.out.print(myAverageTimes[i]+", ");
//		}
		for(myK = 0; myK<200; myK++){
			for(int g = 0; g<ktimes; g++){
				//Making C
				for(int i = 0; i<C.length; i++){
					C[i] = i;
				}
				for(int i = 0; i< (int)Math.round(Math.log(C.length)/Math.log(2)); i++){
					int rng1 = rng.nextInt(C.length); //Random number 0 - C.length
					int rng2 = rng.nextInt(C.length);
					swap(C, rng1, rng2);
				}
				//C
				startTime = System.nanoTime();
				QuickSort(C, 0, C.length-1, myK);
				endTime = System.nanoTime();
				avgCSpeed += (endTime - startTime);
			}
			avgCSpeed = avgCSpeed / ktimes;
			myAverageTimes[myK] = avgCSpeed;
			avgCSpeed = 0;
		}
		for(int i = 0; i<200; i++){
			System.out.print(myAverageTimes[i]+", ");
		}

	}

	//InsertionSort from CLRS
	public static void InsertionSort( double[] A, int p, int r ){
		int j;
		for(j = p+1; j <= r; j++){
			double key = A[j];
			int i = j-1;
			while(i > 0 && A[i] > key){
				A[i+1] = A[i];
				i -= 1;
			}
			A[i+1] = key;
		}
	}

	//QuickSort from CLRS
	public static void QuickSort( double[] A, int p, int r, int k ){
		if( p < r ){
			if(r-p <= k){
				InsertionSort(A, p, r);
			}
			else{
				int q = Partition(A, p, r);
				QuickSort(A, p, q-1, k);
				QuickSort(A, q+1, r, k);
			}
		}
	}

	//Partition process
	public static int Partition( double[] A, int p, int r ){
		double x = A[r];
		int i = p-1;
		for(int j = p; j <= r-1; j++){
			if( A[j] <= x){
				i = i+1;
				swap(A, i, j);
			}
		}
		swap(A, i+1, r);
		return i+1;
	}

	//Helper function swap
	public static void swap( double[] a, int i, int j){
		double k = a[i];
		a[i] = a[j];
		a[j] = k;
	}

	//Helper function shuffle
	// Implementing Fisher–Yates shuffle
	public static void shuffleArray(double[] ar)
	{

	    Random rnd = new Random();
	    for (int i = ar.length - 1; i > 0; i--)
	    {
	      int index = rnd.nextInt(i + 1);
	      // Simple swap
	      double a = ar[index];
	      ar[index] = ar[i];
	      ar[i] = a;
	    }
	  }
}