// JavaBasics.java

// Demonstrates methods, variables, conditionals, arrays, recursion, etc...

class JavaBasics {

	///////////////////////////////////
	/// PrimeDemo
	///////////////////////////////////
	
	public static boolean isDivisibleBy(int n, int k) {
		return (n % k == 0);
	}

	// can speed up by only testing odds and also by only checking
	// up to the square root of n	
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		for (int counter=2; counter<n; counter++)
			if (isDivisibleBy(n,counter))
				return false;
		return true;
	}
	
	public static void primeDemo() {
		for (int n=0; n<20; n++)
			System.out.println(n + ": " + isPrime(n));
	}

	///////////////////////////////////
	/// Recursion Demo
	///////////////////////////////////

	// fib(n) = fib(n-1) + fib(n-2)
	// 1, 1, 2, 3, 5, 8, 13, 21, ...
	public static int fib(int n) {
		// BASE CASE
		if (n < 2)
			return 1;
		// RECURSIVE CASE
		return fib(n-1) + fib(n-2);
	}
	
	// for now, just use a max size of 1000 (not a great solution)
	public static boolean[] memoized = new boolean[1000];
	public static int[] memoizedResult = new int[1000];

	public static int memoizingFib(int n) {
		// IF MEMOIZED, USE COMPUTED RESULT
		if (memoized[n]) return memoizedResult[n];
		// BASE CASE
		int result;
		if (n < 2)
			result = 1;
		// RECURSIVE CASE
		else
			result = memoizingFib(n-1) + memoizingFib(n-2);
		// STORE MEMOIZED RESULT
		memoized[n] = true;
		memoizedResult[n] = result;
		// RETURN RESULT
		return result;
	}
	
	public static int iterativeFib(int n) {
		if (n < 2) return 1;
		int fk = 2, fkMinus1 = 1, fkMinus2 = 1;
		for (int k=1; k<n; k++) {
			fk = fkMinus1 + fkMinus2;
			fkMinus2 = fkMinus1;
			fkMinus1 = fk;
		}
		return fk;
	}

	public static void recursionDemo() {
		System.out.print("Enter first n: ");
		int n = readInt();

		System.out.println("\nUsing 'fib':");
		for (int counter=0; counter<5; counter++)
			System.out.println("fib(" + (n+counter) + ") = " + fib(n+counter));

		System.out.println("\nUsing 'memoizingFib':");
		for (int counter=0; counter<20; counter++)
			System.out.println("fib(" + (n+counter) + ") = " + memoizingFib(n+counter));

		System.out.println("\nUsing 'iterativeFib':");
		for (int counter=0; counter<20; counter++)
			System.out.println("fib(" + (n+counter) + ") = " + iterativeFib(n+counter));
	}
	
	///////////////////////////////////
	/// SortingDemo
	///////////////////////////////////
	
	public static int[] makeRandomArray(int size) {
		int[] array = new int[size];
		// and load it with random numbers between, oh, 1 and 99
		for (int k=0; k<size; k++)
			array[k] = (int)(100*Math.random());
		return array;
	}
	
	public static void printArray(int[] array) {
		for (int i=0; i<array.length; i++)
			System.out.println(array[i]);
	}
	
	public static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	public static void sortArray(int[] array) {
		for (int i=0; i<array.length; i++)
			for (int j=i+1; j<array.length; j++)
				if (array[i] > array[j])
					swap(array,i,j);
	}

	public static void sortingDemo() {
		System.out.print("Enter size of array: ");
		int n = readInt();
		int[] array = makeRandomArray(n);
		System.out.println("Here is the unsorted array:");
		printArray(array);
		sortArray(array);
		System.out.println("\nAnd here is the SORTED array:");
		printArray(array);
	}
	
	///////////////////////////////////
	/// Main
	///////////////////////////////////

	public static void main(String[] args) {
		// primeDemo();
		// recursionDemo();
		sortingDemo();
	}

	///////////////////////////////////
	// readString, readInt, readDouble
	///////////////////////////////////
	
	public static String readString() {
		java.io.InputStreamReader isr = new java.io.InputStreamReader(System.in);
		java.io.BufferedReader d = new java.io.BufferedReader(isr);
		try { return d.readLine(); } catch (Exception e) { return "error"; }
	}
	public static int readInt() { return Integer.parseInt(readString()); }
	public static double readDouble() {
		return Double.valueOf(readString()).doubleValue();
	}
}