import java.util.*;

class TimingBubbleSort2
{
	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 improvedBubbleSort(int[] data, int n)
	{

	        int i = 0;        
		boolean done = false;
        	while(!done)
        	{
                	done =  true;
                	for(int j = n-2; j >= i; j--)
                        	if(data[j] > data[j+1])
                        	{
                                	done = false;
                                	swap(data, j, j+1);
                        	}
                	i++;
        	}

	}

	
	public static void main(String[] args)
	{
		long time, newTime;
		long[] sum1 = new long[10];
		long[] sum2 = new long[10];
		int iter;

		for(int n = 1000; n <= 10000; n=n+1000)
		{
			
			iter = (n-1)/1000;
			sum1[iter] = 0;
			sum2[iter] = 0;
			for (int j = 0; j < 10; j++)
			{
				// Generate an almost sorted integer array of size n
				int[] data1;
				int[] data2;
				data1 = new int[n];
				data2 = new int[n];
				for(int i = 0; i < n; i++)
				{
					data1[i] = n-i-1;
					data2[i] = n-i-1;
				}
			
				// 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 < 10; i++)
				{
					int index1 = rand.nextInt(n);
					int index2 = rand.nextInt(n);
					swap(data1, index1, index2);
					swap(data2, index1, index2);
				}

				// Initialize time to the value before calling
				// bubbleSort and newTime to the value after
				time = System.currentTimeMillis();
				bubbleSort(data1, n);
				newTime  = System.currentTimeMillis();
				sum1[iter] = sum1[iter] + (newTime-time);

				// Initialize time to the value before calling
				// improved bubbleSort and newTime to the value after
				time = System.currentTimeMillis();
				improvedBubbleSort(data2, n);
				newTime  = System.currentTimeMillis();
				sum2[iter] = sum2[iter] + (newTime-time);
			} // end of the 10 iterations for a particular value of n

		} // end of all the iterations

		// Printing the timing numbers
		System.out.print("{");
		for(int i = 0; i < 10; i++)
		{
			if(i < 9)
				System.out.print(sum1[i]*1.0/10+", ");
			else
				System.out.println(sum1[i]*1.0/10+"}");
		}

		System.out.print("{");
		for(int i = 0; i < 10; i++)
		{
			if(i < 9)
				System.out.print(sum2[i]*1.0/10+", ");
			else
				System.out.println(sum2[i]*1.0/10+"}");
		}

	} // end of main function
} // end of class