/*
 * (C) Copyright IBM Corporation. 2004.  All Rights Reserved. 
*/


//Sort.java

import java.util.Random;

/* Class RandNum generates maxArrayLength Random numbers */
class RandNum {

	Random r = new Random();

	int num;

	int numbers[];

	RandNum(int maxArrayLength) {
		numbers = new int[maxArrayLength];
		for (int i = 0; i < maxArrayLength; i++) {
			num = r.nextInt();
			numbers[i] = num;
		}
	}

	int[] getRandNum() {
		return numbers;
	}
}

/* main class Sort */
class Sort {
	
	public static void main(String args[]) {

		int maxArrayLength = 10000;
		RandNum rnum = new RandNum(maxArrayLength);

		int num[] = new int[maxArrayLength];
		int num1[] = new int[maxArrayLength];
		System.arraycopy(rnum.getRandNum(), 0, num, 0, maxArrayLength);
		// num and num1 have identical integer array
		System.arraycopy(num, 0, num1, 0, maxArrayLength);

		// compute median using Bsort
		Bsort(num);
		computemed(num);

		// compute median using Quick sort
		Qsort(num1);
		computemed(num1);

	}

	/* Bubble Sort demonstration algorithm */
	static void Bsort(int rnum[]) {
		bsort(rnum, 0, rnum.length - 1);
	}

	/* Quick Sort demonstration algorithm 
	 * The "quick" method makes extensive use of System.arraycopy() and is slow.
	 * The "quickFast" method is faster because it does not use System.arraycopy().
	 */
	static void Qsort(int rnum[]) {
		// To switch to quickFast, comment out the following 2 lines and
		// remove the comment characters from the 3rd line
		int numOut[] = quick(rnum, 0, rnum.length - 1);
		System.arraycopy(numOut, 0, rnum, 0, rnum.length); 
		// quickFast(rnum, 0, rnum.length - 1);
	}
	
	static void bsort(int rnum[], int lo0, int hi0) {
		int lastIndex = hi0;
		for (int j = lo0; j<hi0; j++) {
			for (int i = lo0; i < lastIndex; i++) {
				if (rnum[i] > rnum[i + 1]) {
					int temp = rnum[i];
					rnum[i] = rnum[i + 1];
					rnum[i + 1] = temp;
				}
			}
			lastIndex--;
		}
//		if (hi0 > 1)
//			bsort(rnum, lo0, hi0 - 1);
	}

	
	static int[] quick(int inNum[], int lo0, int hi0) {
		int lo = lo0;
		int hi = hi0;
		int numbers[] = new int[inNum.length];
		System.arraycopy(inNum, 0, numbers, 0, inNum.length);

		if (lo >= hi) {
			return numbers;
		} else if (lo == hi - 1) {
			if (numbers[lo] > numbers[hi]) {
				int T = numbers[lo];
				numbers[lo] = numbers[hi];
				numbers[hi] = T;
			}
			return numbers;
		}
		int pivot = numbers[(lo + hi) / 2];
		numbers[(lo + hi) / 2] = numbers[hi];
		numbers[hi] = pivot;

		while (lo < hi) {

			/* Search forward until element is found that is greater than the pivot */
			while (numbers[lo] <= pivot && lo < hi) {
				lo++;
			}
			
			/* Search backward until element is found that is less than the pivot */
			while (pivot <= numbers[hi] && lo < hi) {
				hi--;
			}
			
			/*  Swap elements a[lo] and a[hi] */
			if (lo < hi) {
				int T = numbers[lo];
				numbers[lo] = numbers[hi];
				numbers[hi] = T;
			}
		}
		
		/*  Put the median in the "center" of the list */
		numbers[hi0] = numbers[hi];
		numbers[hi] = pivot;

		/*  Recursive calls */
		int outNum[] = quick(numbers, lo0, lo - 1);
		System.arraycopy(outNum, lo0, numbers, lo0, lo-lo0);
		outNum = quick(numbers, hi + 1, hi0);
		System.arraycopy(outNum, hi+1, numbers, hi+1, hi0-hi);
		return numbers;
	}

	/* Quick Sort demonstration algorithm */
	static void quickFast(int numbers[], int lo0, int hi0) {
		int lo = lo0;
		int hi = hi0;

		if (lo >= hi) {
			return;
		} else if (lo == hi - 1) {
			if (numbers[lo] > numbers[hi]) {
				int T = numbers[lo];
				numbers[lo] = numbers[hi];
				numbers[hi] = T;
			}
			return;
		}
		int pivot = numbers[(lo + hi) / 2];
		numbers[(lo + hi) / 2] = numbers[hi];
		numbers[hi] = pivot;

		while (lo < hi) {

			/* Search forward until element is found that is greater than the pivot */
			while (numbers[lo] <= pivot && lo < hi) {
				lo++;
			}
			
			/* Search backward until element is found that is less than the pivot */
			while (pivot <= numbers[hi] && lo < hi) {
				hi--;
			}
			
			/*  Swap elements a[lo] and a[hi] */
			if (lo < hi) {
				int T = numbers[lo];
				numbers[lo] = numbers[hi];
				numbers[hi] = T;
			}
		}
		
		/*  Put the median in the "center" of the list */
		numbers[hi0] = numbers[hi];
		numbers[hi] = pivot;

		/*  Recursive calls */
		quickFast(numbers, lo0, lo - 1);
		quickFast(numbers, hi + 1, hi0);
	}
	
	/* Compute Median for the sorted array */
	static void computemed(int rnum[]) {

		int medIndex = rnum.length;
		int median;

		switch (medIndex) {
		case 0:
			median = 0;
			break;
		case 1:
			median = rnum[0];
			break;
		default: // 2 and above
			if (medIndex % 2 == 0) {
				medIndex = medIndex / 2;
				median = (rnum[medIndex - 1] + rnum[medIndex]) / 2;
			} else {
				median = (rnum[medIndex / 2]);
			}
		}

		System.out.println("\n***************************************\n");

		if (rnum.length > 0)
			System.out.println("Median of  " + rnum.length
					+ "  sorted numbers is : " + median);
		else
			System.out.println("Median of  " + rnum.length
					+ "  sorted numbers is : unknown");

		System.out.println("\n*****************************************\n");
		
	}


}