import java.util.*;

class TimingSimpleSort
{
	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 selectionSort(int[] data, int n)
	{
  		int i, j, min;
 
  		for (i = 0; i < n-1; i++)
  		{
			// Select the minimum element from the remaining
			// and swap into position i
    			min = i;

    			for (j = i+1; j < n; j++)
       				if (data[j] < data[min])
          				min = j;

    			swap(data, i, min);
  		}
	}

        public static void insertionSort(int[] data, int n)
        {
                for(int i = 1; i < n-1; i++)
                {
                        // This is the value that needs to be inserted
                        int value = data[i];

                        // Scan the first i elements, starting at the end
                        // and shifting them while scanning
                        int j = i-1;
                        while((j >= 0) && (data[j] > value))
                        {
                                data[j+1] = data[j];
                                j--;
                        }

                        data[j+1] = value;


                }
        }

	
	public static void main(String[] args)
	{
		long time, newTime, bubbleSum, selectSum, insertSum;

		System.out.println("Bubble Selection Insertion");
		for(int n = 1000; n <= 20000; n=n+1000)
		{

			// Initialize running time sums
			bubbleSum = 0;
			insertSum = 0;
			selectSum = 0;

			for (int j = 0; j < 10; j++)
			{
				// Generate a random integer array of size n
				int[] data1, data2, data3;
				data1 = new int[n];
				data2 = new int[n];
				data3 = 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++)
				{
					data1[i] = rand.nextInt();
					data2[i] = data1[i];
					data3[i] = data1[i];
				}

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

				bubbleSum = bubbleSum + (newTime-time);


                                // Initialize time to the value before calling
                                // selection Sort and newTime to the value after
                                time = System.currentTimeMillis();
                                selectionSort(data2, n);
                                newTime  = System.currentTimeMillis();

                                selectSum = selectSum + (newTime-time);


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

                                insertSum = insertSum + (newTime-time);




			}

			System.out.println(bubbleSum*1.0/10 + " " + selectSum*1.0/10 + " " + insertSum*1.0/10);
		}
	}
}