public class IntSortMain
{
	public static void main (String[ ] args)
	{
		int[ ] intArray = {59,  46,  32,  80,  46,  55,  50,  43,  44,  81,
				  12,  95,  17,  80,  75,  33,  40,  61,  16,  87};

		//insertionSort (intArray);
		//selectionSort (intArray);
		bubbleSort (intArray);
		for (int i : intArray)
			System.out.print (i + " ");
	} // method main

	/**
	 *  Sorts a specified array of int values into ascending order.
	 *  The worstTime(n) is O(n * n).
	 *
	 *  @param x - the array to be sorted.	 
	 *
	 */	
	public static void insertionSort (int[ ] x) 
	{
		for (int i = 1; i < x.length; i++)
	       		for (int j = i; j > 0 && x [j -1] > x [j]; j--)
		    		swap (x, j, j -1);
	} // method insertionSort



	/**
	 *  Swaps two specified elements in a specified array.
	 *
	 *  @param x - the array in which the two elements are to be swapped.
	 *  @param a - the index of one of the elements to be swapped.
	 *  @param b - the index of the other element to be swapped.
	 *
	 */
	public static void swap (int [ ] x, int a, int b) 
	{
		int t = x[a];
		x[a] = x[b];
		x[b] = t;
	} // method swap


	/**
	 *  Sorts a specified array of int values into ascending order.
	 *  The worstTime(n) is O(n * n).
	 *
	 *  @param x - the array to be sorted.
	 *
	 */
	public static void selectionSort (int [ ] x) 
	{
		// Make x [0 ... i] sorted and <= x [i+1 ... x.length-1]:
		for (int i = 0; i < x.length - 1; i++) 
		{
          		int pos = i;
          		for (int j = i + 1; j < x.length; j++)
              			if (x [j] < x [pos]) 
                  			pos = j;
          		swap (x, i, pos);
      		} // for i
  	} // method selectionSort


	/**
	 *  Sorts a specified array of int values into ascending order.
	 *  The worstTime(n) is O(n * n).
	 *
	 *  @param x - the array to be sorted.
	 *
	 */
  	public static void bubbleSort (int[ ] x) 
	{
        	int finalSwapPos = x.length - 1,
                    swapPos;             	

        	while (finalSwapPos > 0)
		{
             		swapPos = 0;
             		for (int i = 0; i < finalSwapPos; i++)
                 		if (x [i] > x [i + 1])
                 		{
                     			swap (x, i, i + 1);
                     			swapPos = i;
                 		} // if
             		finalSwapPos = swapPos;             
        	} // while      
  	} // method bubbleSort

} // class IntSortMain