import java.util.*;

class TimingBubbleSort
{
	public static void swap(int[] data, int x, int y)
	{
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}

	public static void bubbleSort(int[] data, int n)
	{
		for(int i = 0; i < n-1; i++)
		{	
			for(int j = n-2; j >= i; j--)
			{
				if(data[j+1] < data[j])
					swap(data, j, j+1);
			}
		}
	}
	
	public static void main(String[] args)
	{
		long time, newTime, sum;

		System.out.print("{");
		for(int n = 1000; n <= 20000; n=n+1000)
		{

			sum = 0;
			for (int j = 0; j < 10; j++)
			{
				// Generate a random integer array of size n
				int[] data;
				data = new int[n];
			
				// Random is a java class defined in java.util	
				// To learn more about this class see 
				// http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html
				Random rand;
				rand = new Random();

				for(int i = 0; i < n; i++)
					data[i] = rand.nextInt();

				// Initialize time to the value before calling
				// bubbleSort and newTime to the value after
				time = System.currentTimeMillis();
				bubbleSort(data, n);
				newTime  = System.currentTimeMillis();

				sum = sum + (newTime-time);
			}

			if(n < 20000)
				System.out.print(sum*1.0/10+", ");
			else
				System.out.println(sum*1.0/10+"}");
		}
	}
}