Insertion Sort

/*nth element would require n comparison operations .That means total time consumed would be 1+2+3+4+.......+n which is a function of n*n
A great video on insertion sort is here
http://www.youtube.com/watch?v=c4BRHC7kTaQ
*/



/*Java Program for Insertion sort*/

import java.util.*;


public class InsertionSort {
public static void main (String args[])
{
/*Take the input into ArrayList using scanner*/
ArrayList InputArrayList = new ArrayList();
System.out.println("Give the input array, It will take the input until you press a non numeric key");
Scanner scan = new Scanner(System.in);
while(scan.hasNextInt())
{
InputArrayList.add(scan.nextInt());
}
System.out.println("ArrayList is " + InputArrayList);
/*Convert the ArrayList to IntegerArray */
int i, SIZE=InputArrayList.size();
int[] InputArrayInt= new int[SIZE];
int[] OutputArrayInt= new int[SIZE];
for(i=0;iInputArrayInt[i]=InputArrayList.get(i);
/*pass this array to insertsort function for sorting and collect it to OutputArrayInt*/
OutputArrayInt=insertsort(InputArrayInt);
/*Display the output array*/
System.out.println("The sorted array is ");
for(i=0;iSystem.out.println(OutputArrayInt[i]);
}
public static int[] insertsort(int[] IAInt)
{
int lenth= IAInt.length;
int i, j,temp;
for(i=1;i{
for(j=i-1;j>=0;j--)
{
if(IAInt[i]{
temp=IAInt[j];
IAInt[j]=IAInt[i];
IAInt[i]=temp;
i=j;/*This is an important step , now the if comparison would be from new position of i after swapping*/
}
}
}
return(IAInt);
}
}