class Sorting {
	public static void main(String args[]){
		int [] l={66,33,4,5,6,2,23,54,32,34,2,1,5};
		insertionSort(l);
		System.out.println(arrayToString(l));
	}

	// An inplace sort (requires no extra space)
	// put the elements in list in ascending order
	public static void insertionSort(int [] list){
		// Algorithm: for each i, put 
		// list[i] where it belongs in list[0..i-1]
		// moving the larger elements up

		// Inv: list[0..i-1] is a sorted sequence of the 
		//      first i members originally in list
		for(int i=1;i<list.length;i++){
			int t=list[i]; int j=i;
			// Inv: list[j+1..i] are the largest elements  
			// originally (before the while loop) in list[j..i-1] 
			while(j!=0 && list[j-1]>t){
				list[j]=list[j-1];
				j--;
			}
			// Now all necessary elements have been shifted. Insert t
			list[j]=t;
		}
	}

	// An inplace sort (requires no extra space)
	// put the elements in list in ascending order
	public static void selectionSort(int [] list){
		// Algorithm: For each i, find the member of list
		// that belongs in that location, put it there, moving
		// all other elements up
		
		// Inv: list[0..i-1] is a sorted sequence of the 
		//      i smallest members originally in list


	}

	public static String arrayToString(int [] a){
		String s="";
		for(int i=0;i<a.length;i++){
			s+=" "+a[i];
		}
		return(s);
	}
}