import java.util.Random;

/* Learning to do sorting 
   (L) Copyleft Linus Walleij 2001 */

class Sorting {
    private long timer = System.currentTimeMillis();
    
    /* Empty constructor... */
    public Sorting() {}

    /* Main method for running tests */
    public static void main(String[] args) {
	int runSize = 0;
	try {
	    runSize = Integer.parseInt(args[0]);
	} catch (NumberFormatException e) {
	    System.err.println("Usage: java Sorting <num>");
	    System.err.println("where <num> is number of random integers to test with.");
	    System.exit(1);
	}
	Sorting mySorting = new Sorting();
	mySorting.runTest(runSize);
    }

    private void setTimer() {
	timer = System.currentTimeMillis();
    }
    private long getTimer() {
	return System.currentTimeMillis()-timer;
    }

    private void runTest(int size) {
	long now;
	int[] foo = new int[size];
	int[] bubAr = new int[size];
	int[] insAr = new int[size];
	int[] sheAr = new int[size];
	int[] merAr = new int[size];
	int[] qikAr = new int[size];
	int[] radAr = new int[size];

	/* Create a set of equal random arrays */
	Random myRandom = new Random();
	for (int i = 0; i < size; i++)
	    foo[i] = myRandom.nextInt(999)+1;
	for (int i = 0; i < size; i++) {
	    bubAr[i] = foo[i];
	    insAr[i] = foo[i];
	    sheAr[i] = foo[i];
	    merAr[i] = foo[i];
	    qikAr[i] = foo[i];
	    radAr[i] = foo[i];
	}
	System.out.println("Created random array of size: " + size);

	// printArray(foo);

	/* Sort it */
	System.out.print("Bubble sort...... ");
	setTimer();
	bubbleSort(bubAr);
	System.out.println(getTimer() + "ms");

	System.out.print("Insertion sort... ");
	setTimer();
	insertionSort(insAr);
	System.out.println(getTimer() + "ms");

	System.out.print("Shell sort....... ");
	setTimer();
	shellSort(sheAr);
	System.out.println(getTimer() + "ms");

	System.out.print("Merge sort....... ");
	setTimer();
	mergeSort(merAr);
	System.out.println(getTimer() + "ms");

	System.out.print("Quick sort....... ");
	setTimer();
	quickSort(qikAr);
	System.out.println(getTimer() + "ms");

	System.out.print("Radix sort....... ");
	setTimer();
	radixSort(radAr);
	System.out.println(getTimer() + "ms");

	// printArray(foo);
    }

    public void printArray(int[] theArray) {
	/* print it */
	for (int i = 0; i < theArray.length; i++)
	    System.out.print(theArray[i] + " ");
	System.out.println();
    }

    public void bubbleSort(int[] theArray) {
	/* Simple bubbleSort O(n^2)? */
	boolean finished = false;
	while (!finished) {
	    for (int i = 1; i < theArray.length; i ++)
		if (theArray[i] < theArray[i-1]) {
		    int tmp = theArray[i];
		    theArray[i] = theArray[i-1];
		    theArray[i-1] = tmp;
		    break;
		} else if (i == theArray.length-1)
		    finished = true;
	}
    }

    public void insertionSort(int[] theArray) {
	/* Simple insertionSort O(n^2) */
	for (int i = 0; i < theArray.length; i++)
	    for (int j = i; j > 0; j--) {
		if (theArray[j] < theArray[j-1]) {
		    int tmp = theArray[j-1];
		    theArray[j-1] = theArray[j];
		    theArray[j] = tmp;
		}
		else break;
	    }
    }

    public void shellSort(int[] theArray) {
	/* Shell sort - invented by Donald Shell 1959 
	   Gonnet suggested using 2.2 division of gap 
	   for each iteration */
	for (int gap = theArray.length/2; gap > 0; gap = gap == 2 ? 1 : (int) (gap / 2.2)) {
	    for (int i = gap; i < theArray.length; i++) {
		for (int j = i; j >= gap; j -= gap) {
		    if(theArray[j] < theArray[j-gap]) {
			int tmp = theArray[j-gap];
			theArray[j-gap] = theArray[j];
			theArray[j] = tmp;
		    }
		}
	    }
	}
    }

    public void mergeSort(int[] theArray) {
	/* Recursive mergeSort O(n log n) */
	mergeSort(theArray, 0, theArray.length-1);
    }
    private void mergeSort(int[] theArray, int beginning, int end) {
	if (end <= beginning) {
	    return;
	} else {
	    int mid = beginning + (end-beginning)/2;
	    mergeSort(theArray, beginning, mid);
	    mergeSort(theArray, (mid+1), end);
	    int[] tmpArray = new int[end-beginning+1];
	    int leftP = beginning;
	    int rightP = mid+1;
	    int tmpP = 0;
	    while (tmpP < tmpArray.length) {
		if (rightP == end+1 || leftP < mid+1 && theArray[leftP] <= theArray[rightP]) {
		    tmpArray[tmpP] = theArray[leftP];
		    leftP ++;
		} else {
		    tmpArray[tmpP] = theArray[rightP];
		    rightP ++;
		}
		tmpP ++;
	    }
	    for (int i = 0; i < tmpArray.length; i++)
		theArray[beginning+i] = tmpArray[i];
	}
    }
    
    public void quickSort(int[] theArray) {
	quickSort(theArray, 0, theArray.length-1);
    }
    
    private void quickInsertionSort(int[] theArray, int beginning, int end) {
	for (int i = beginning; i < end+1; i++) {
	    for (int j = i; j > beginning; j--) {
		if (theArray[j] < theArray[j-1]) {
		    int tmp = theArray[j-1];
		    theArray[j-1] = theArray[j];
		    theArray[j] = tmp;
		}
	    }
	}
    }
    
    private void quickSort(int[] theArray, int beginning, int end) {
	/* Quick sort best of three, insertion sort under LIMIT */
	final int LIMIT = 5;
	if (end-beginning <= LIMIT)
	    quickInsertionSort(theArray, beginning, end);
	else {
	    int pivotpos = beginning + (end-beginning)/2;
	    int pivot; /* of the type compared */
	    int[] tmpArray = new int[3];
	    int leftP = beginning; /* beginning already correct */
	    int rightP = end-1; /* end and end-1 will already be correct */

	    tmpArray[0] = theArray[beginning];
	    tmpArray[1] = theArray[pivotpos];
	    tmpArray[2] = theArray[end];
	    quickInsertionSort(tmpArray,0,2);

	    theArray[beginning] = tmpArray[0];
	    pivot = tmpArray[1];
	    theArray[end] = tmpArray[2];
	    theArray[pivotpos] = theArray[end-1];
	    theArray[end-1] = pivot; // Unnecessary

	    while (true) {
		while (theArray[++leftP] < pivot)
		    ;
		while (theArray[--rightP] > pivot)
		    ;
		if (rightP > leftP) {
		    int tmp = theArray[rightP];
		    theArray[rightP] = theArray[leftP];
		    theArray[leftP] = tmp;
		} else
		    break;
	    }
	    pivotpos = leftP;
	    theArray[end-1] = theArray[pivotpos];
	    theArray[pivotpos] = pivot;
	    quickSort(theArray, beginning, pivotpos-1);
	    quickSort(theArray, pivotpos+1, end);
	}
    }

    public void radixSort(int[] theArray) {
	/* Radix sort this array byte0, byte1, byte2, byte3 ... It's integers! */
	int[] tmpArray = new int[theArray.length];
	radix((short) 0, theArray, tmpArray);
	radix((short) 1, tmpArray, theArray);
	radix((short) 2, theArray, tmpArray);
	radix((short) 3, tmpArray, theArray);
    }
    
    private void radix(short bitOffset, int[] source, int[] dest) {
	long count[] = new long[256];
	long index[] = new long[256];
	for (int i=0; i < source.length; i++)
	    count[((source[i]) >> (bitOffset*8)) & 0xff]++;
	for (int i=1; i<256; i++) index[i]=index[i-1]+count[i-1];
	for (int i=0; i<dest.length; i++) dest[(int) index[((source[i]) >> (bitOffset*8)) & 0xff]++] = source[i];
    }
}