/****************SELECTION ***********************************************
 *************************************************************************/
 
 // FromKoffman & Wolfgang, Data Structures, 2nd ed

//  page 426 - 7

public class SelectionSort {

	public static void sort (int[] table) {
		int n = table.length;
		for (int i=0; i<n-1; i++) {
			int pos = i;
			for (int j = i+1; j < n; j++) {
				if (table[j] <table[pos]) pos = j;
			}                                         // for j
			
			// swap table[i] and table[pos]
			int temp = table[i];
			table[i] = table[pos];
			table[pos] = temp;
			}                                         // for i
		}                                               // public sort
	

	
	public static void main(String[] args) {
		int[] arr = {5, 10, 15, 14, 9, 4, 11};
		
		System.out.println("arr unsorted: ");
		for (int i=0; i<arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();
		
		sort(arr);
		
		System.out.println("arr sorted: ");
		for (int i=0; i<arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();

	}

}


/*****************************************************************************
						BUBBLE
 *****************************************************************************/
 
 // Koffman & Wolfgang, DataStructures pp 430 - 1


public class BubbleSort {

	public static void sort (int[] table) {
		int pass = 1;
		boolean exchanges = false;
		
		do {
			exchanges = false;
			
			for (int i = 0; i<table.length - pass; i++) {
				if (table[i] > table[i+1]) {
					int t = table[i];
					table[i] = table[i+1];
					table[i+1] = t;
					exchanges = true;
				}                                    // if
			}                                           // for i
			pass++;
			} while (exchanges);
		}                                               // public sort

	
	
	public static void main(String[] args) {
		int[] arr = {5, 10, 15, 14, 9, 4, 11};
		
		System.out.println("arr unsorted: ");
		for (int i=0; i<arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();
		
		sort(arr);
		
		System.out.println("arr sorted: ");
		for (int i=0; i<arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();

	}

}


/*****************************************************************************
						INSERTION
 *****************************************************************************/

public class InsertionSort {
	// Koffman & Wolfgang, DataStructures pp 434-5

	public static void sort (int[] table) {
		for (int i = 1; i < table.length; i++) {
			insert(table, i);
		}                                            // for i
	}                                                   // public sort

	public static void insert(int[] table, int i) {
		int val = table[i];
		while (i > 0 && val < table[i-1]) {
			table[i] = table[i-1];
			i--;
		}                                               // while
		
		table[i] = val;
	}                                                   //  public insert
		
		
	public static void main(String[] args) {
		int[] arr = {5, 10, 15, 14, 9, 4, 11};
		
		System.out.println("arr unsorted: ");
		for (int i=0; i<arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();
		
		sort(arr);
		
		System.out.println("arr sorted: ");
		for (int i=0; i<arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();
		}

}