public class Sorting
{
	public static void main( String args[] )
	{
		int arr1[] = { 53, 10, 2, 62, 128, 93, 28, 18 };
		insertionSort( arr1 );
		printArray( arr1 );
		int arr2[] = { 53, 10, 2, 62, 128, 93, 28, 18 };
		selectionSort( arr2 );
		printArray( arr2 );
		int arr3[] = { 53, 10, 2, 62, 128, 93, 28, 18 };
		bubbleSort( arr3 );
		printArray( arr3 );
	}

	public static void printArray( int s[] )
	{
		for( int i = 0; i < s.length; i++ )
		{
			System.out.print( s[i] + " " );
		}
		System.out.println();
	}

	public static void insertionSort( int s[] )
	{
		int n = s.length;
		for( int i = 1; i < n; i++ )
		{
			int j;
			int temp = s[i]; // incoming element
			for( j = i; j > 0 && s[j-1] > temp; j-- ) // adjust elements to the right
			{
				s[j] = s[j-1];
			}
			s[j] = temp; // insert incoming element
		}

	}

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

	}

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

	}

}