public class BasicSorts {

	public static void bubbleSort( int [] data, int ndata )
	{

		if( ndata <= 1 )
			return;

		for ( int pass = 1; pass < ndata; pass ++ )
		{
			int lastIdx = ndata - 1;
			for ( int itemIdx = 0; itemIdx < lastIdx; itemIdx ++ )
			{
				if ( data[ itemIdx ] > data[ itemIdx + 1] )
				{
					int temp = data[ itemIdx ];
					data[ itemIdx ] = data[ itemIdx + 1 ];
					data[ itemIdx + 1 ] = temp;
				}
			}
		}
	}
	
	public static void insertionSort( int [] data, int ndata )
	{

		if( ndata <= 1 )
			return;

		/* Find the smallest element and swap it with data[0]. */
		int minItemIdx = 0;
		for( int k = 1; k < ndata; k ++ )
		{
			if( data[minItemIdx] > data[k] )
				minItemIdx = k;
		}
		if( minItemIdx != 0 )
		{
			int temp = data[0];
			data[0] = data[minItemIdx];
			data[minItemIdx] = temp;
		}

		// data[0] <= data[1]
		for( int itemIdx = 2; itemIdx < ndata; itemIdx ++ )
		{
			/* data[0] <= data[1] <= ... <= data[itemIdx -1].
		     insert data[itemIdx] into the sequence. */
			int k;
			int temp = data[itemIdx];
			for( k = itemIdx; temp < data[k-1]; k-- )
			{
				data[k] = data[k-1];   /* move down */
			}
			data[k] = temp;		     /* insert into sequence */
		}
	}
	
	public static void insertionSort2( int [] data, int ndata )
	{

		if( ndata <= 1 )
			return;

		for( int itemIdx = 1; itemIdx < ndata; itemIdx ++ )
		{
			/* data[0] <= data[1] <= ... <= data[itemIdx -1].
		     insert data[itemIdx] into the sequence. */
			int temp = data[itemIdx];
			int k = itemIdx - 1;
			while( k >= 0  && temp < data[k] )
			{
				data[k+1] = data[k];   /* move down */
				-- k;
			}
			data[k+1] = temp;		     /* insert into sequence */
		}
	}
	
	public static void selectionSort( int [] data, int ndata )
	{

		for ( int pass = 1; pass < ndata; pass ++ )
		{
			int minItemIdx = pass - 1;      // index to the current minimum item
			for ( int itemIdx = pass; itemIdx < ndata; itemIdx ++ )
			{
				if ( data[ itemIdx ] < data[ minItemIdx ] )
					minItemIdx = itemIdx;
			}

			if ( minItemIdx != pass - 1 )
			{
				int temp = data[ pass - 1 ];
				data[ pass - 1 ] = data[ minItemIdx ];
				data[ minItemIdx ] = temp;
			}
		}
	}

}