import java.util.Random;
public class QsortTest
{
    public static void main (String [] args)
    {
	Comparable [] a;
	Random   ran;
	ConsoleReader console = new ConsoleReader(System.in);

	System.out.println("How many randomly generated integers to sort?");
	int n = console.readInt();

	ran  = new Random();
	a    = new Comparable[n]; // get array of this number of objects
	for (int i=0;i<n;i++)
        {
	   a[i] = new Integer(ran.nextInt(100));
	}

	System.out.println("\nOriginal Array:");
	printArray(a);	
	
	quicksort(a);

	System.out.println("\n\nSorted Array:");
	printArray(a);
    } // end main

// --------------------------------------------------------------

    public static void printArray(Comparable [] a)
    {
	for (int i=0;i<a.length;i++){
	    int j = ((Integer) a[i]).intValue();
	    System.out.print(j + " ");
	}
	System.out.println();
    }

// --------------------------------------------------------------
// driver to recursive sort array of Comaprables using quicksort
// with median of 3 partition. Use insertion sort for small arrays

    public static void quicksort(Comparable [] a)
    {
	quicksort(a,0,a.length-1);
    }

    private static void quicksort(Comparable [] a, int left, int right)
    {
	final int CUTOFF = 3;
	if (right-left+1 < CUTOFF) { // need at least 3 elements for qs
	    insertionSort(a,left,right);
	}
	else {
	    Comparable pivot = median3(a,left,right); // get pivot

	    int i = left, j = right-1;     	      // do the partitioning
	    while (i < j){
		while (a[++i].compareTo(pivot) < 0) {}; // advance left ptr
		while (a[--j].compareTo(pivot) > 0) {}; // decrement rt ptr
		swap(a,i,j);
	    } // end while
	    
	    swap(a,i,j);        // undo last (incorrect) swap
	    swap(a,i, right-1);   // restore pivot
	    
	    quicksort(a,left,i-1);   // recursive calls on smalelr
	    quicksort(a,i+1,right);  // and larger subarrays
	} // end else

    } // end quicksort

// --------------------------------------------------------------

// median of 3 partitioning - put the 3 in order, and hide pivot
    private static Comparable median3(Comparable [] a, int left, int right)
    {
	int center = (left+right)/2;
	if (a[center].compareTo(a[left]) < 0)
	    swap(a,left,center);

	if (a[right].compareTo(a[left]) < 0)
	    swap(a,left,right);

	if (a[right].compareTo(a[center]) < 0)
	    swap(a,center,right);

	// put pivot at NEXT to rightmost position
	swap(a,center,right-1);
	return a[right-1];    // return the pivot too
	    
    }

// --------------------------------------------------------------

// swap the elements at index i and j
    private static void swap(Comparable a[], int i, int j)
    {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
    }

    private static void insertionSort(Comparable a[], int left, int right)
    {
	int j;

	for (int p=left+1; p<= right; p++){
	    Comparable tmp = a[p];
	    for (j=p; j>left && tmp.compareTo( a[j-1]) < 0; j--)
		a[j] = a[j-1];
	    a[j] = tmp;
	}

    } // end insertionSort

} // end class QsortTest