import java.util.*;

class TimingSortingFunctions
{	
public static void bubbleSort(int[] a, int nElems)
      {
      int out, in;

      for(out=nElems-1; out>1; out--)   // outer loop (backward)
         for(in=0; in<out; in++)        // inner loop (forward)
            if( a[in] > a[in+1] )       // out of order?
               swap(a,in, in+1);          // swap them
      }  // end bubbleSort()
//--------------------------------------------------------------
   public static void swap(int[] a, int one, int two)
      {
      int temp = a[one];
      a[one] = a[two];
      a[two] = temp;
      }
	
   public static void recMergeSort(int[] workSpace, int[] theArray, int lowerBound,
                                               int upperBound)
      {
      if(lowerBound == upperBound)            // if range is 1,
         return;                              // no use sorting
      else
         {                                    // find midpoint
         int mid = (lowerBound+upperBound) / 2;
                                              // sort low half
         recMergeSort(workSpace, theArray, lowerBound, mid);
                                              // sort high half
         recMergeSort(workSpace, theArray, mid+1, upperBound);
                                              // merge them
         merge(workSpace,theArray, lowerBound, mid+1, upperBound);
         }  // end else
      }  // end recMergeSort()
   //-----------------------------------------------------------
   public static void merge(int[] workSpace, int[] theArray, int lowPtr,
                           int highPtr, int upperBound)
      {
      int j = 0;                             // workspace index
      int lowerBound = lowPtr;
      int mid = highPtr-1;
      int n = upperBound-lowerBound+1;       // # of items

      while(lowPtr <= mid && highPtr <= upperBound)
         if( theArray[lowPtr] < theArray[highPtr] )
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <= mid)
         workSpace[j++] = theArray[lowPtr++];

      while(highPtr <= upperBound)
         workSpace[j++] = theArray[highPtr++];

      for(j=0; j<n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()

   public static void recQuickSort(int[] theArray, int left, int right)
      {
      int size = right-left+1;
      int median = medianOf3(theArray, left, right);
      int partition = partitionIt(theArray, left, right, median);
      recQuickSort(theArray, left, partition-1);
      recQuickSort(theArray, partition+1, right);
         
      }  // end recQuickSort()
//--------------------------------------------------------------
   public static int medianOf3( int[] theArray, int left, int right)
      {
      int center = (left+right)/2;
                                       // order left & center
      if( theArray[left] > theArray[center] )
         swap(theArray, left, center);
                                       // order left & right
      if( theArray[left] > theArray[right] )
         swap(theArray, left, right);
                                       // order center & right
      if( theArray[center] > theArray[right] )
         swap(theArray, center, right);

      swap(theArray, center, right-1);           // put pivot on right
      return theArray[right-1];        // return median value
      }  // end medianOf3()
//--------------------------------------------------------------
    public static int partitionIt(int[] theArray, int left, int right, int pivot)
       {
       int leftPtr = left;             // right of first elem
       int rightPtr = right - 1;       // left of pivot
       while(true)
          {
          while( theArray[++leftPtr] < pivot )  // find bigger
             ;                                  // (nop)
          while( theArray[--rightPtr] > pivot ) // find smaller
             ;                                  // (nop)
          if(leftPtr >= rightPtr)      // if pointers cross,
             break;                    //    partition done
          else                         // not crossed, so
             swap(theArray, leftPtr, rightPtr);  // swap elements
          }  // end while(true)
       swap(theArray,leftPtr, right-1);         // restore pivot
       return leftPtr;                 // return pivot location
       }  // end partitionIt()

	public static void main(String[] args)
	{
		long time,time2,time3,newTime, newTime2, newTime3, sum, sum2, sum3;
		int[] data,data2,data3;
		System.out.println("{Bubble,Merge,Quick}[ ");
		
		for(int n = 1000; n <= 10000; n=n+1000)
		{
			System.out.print("n="+ n +" {");
			int[] workSpace = new int[n];
			sum = 0;
			sum2 = 0;
			sum3 = 0;
			for (int j = 0; j < 10; j++)
			{
				// Generate a random integer array of size n
				
				data = 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++)
					data[i] = rand.nextInt();
				
				data2 = data;
				data3 = data;
				// 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);
		
				// Initialize time to the value before calling
				// recMergeSort and newTime to the value after
				time2 = System.currentTimeMillis();
				recMergeSort(workSpace,data2,0, (n-1));
				newTime2  = System.currentTimeMillis();

				sum2 = sum2 + (newTime2-time2);
				
				time3 = System.currentTimeMillis();
				recQuickSort(data3,0, n-1);  //will not execute correctly
				newTime3  = System.currentTimeMillis();

				sum3 = sum3 + (newTime3-time3);
		}

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

			}
			System.out.print("]");
		
	}
}