/*
 * Created on Aug 4, 2005
 * 
 * CPS 006 - Summer 05
 * Sam Slee
 * Bubble.java
 * 
 * 
 */

/**
 * @author sslee
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class Bubble {

	//---------------------------------------------------------------------------------
	// Demonstrates the Bubble Sort algorithm.
	public static void main(String[] args) {
		int[] random = {8, 36, 27, 25, 15, 13, 19, 5, 9, 34, 10, 11, 7, 
				33, 6, 30, 14, 3, 18, 22, 32, 16, 1, 20, 24, 
				26, 2, 4, 17, 23, 29, 31, 12, 21, 28, 35};

		int[] reverse = {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25,
				24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
				12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		int[] input = random;
		int goal = 0;
		
		System.out.println("Array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
		
		System.out.println("\n\nSorting with Bubble Sort \n");
		
		bubbleSort(input);
		
		System.out.println("Sorted array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
	}
	
	
	//---------------------------------------------------------------------------------
	// Sorts the given array entries in ascending order
	// using Bubble Sort - O(n^2) time
	public static void bubbleSort(int[] input){
		
		int temp;	// temporary holding variable for swapping
		
		// keep increasing the index marking the end
		// of the sorted portion of our array
		for(int i=0; i<input.length; i++){
			
			// keep swapping values down the line until
			// we reach the sorted portion of our array: input[0.. i]
			for(int j=input.length-1; j>i; j--){
				
				// if the array entry further up holds a smaller value
				// - swap the two values
				if(input[j] < input[j-1]){
					temp = input[j-1];
					input[j-1] = input[j];
					input[j] = temp;
				}
			}
		}
	}
}