Concepts and Code for U

/** this is a program to implement Insertion sort
V.S.Phanindra
*/

/**
Algorithm Analysis
The insertion sort works just like its name suggests - it inserts each item into its proper place in the final
list. The simplest implementation of this requires two list structures - the source list and the list into
which sorted items are inserted. To save memory, most implementations use an in-place sort that works by
moving the current item past the already sorted items and repeatedly swapping it with the preceding item
until it is in place.
Like the bubble sort, the insertion sort has a complexity of O(n2). Although it has the same complexity,
the insertion sort is a little over twice as efficient as the bubble sort.

Pros: Relatively simple and easy to implement.
Cons: Inefficient for large lists.
*/
class InsertionSort
{
public static void main(String[] args)
{
int a[]={2,1,4,6,8,9,-1,4,3,10};
int temp,j;

for(int i=0;i<a.length;i++)
{
int index=a[i];
j=i;
while((j>0)&&(a[j-1]>index))
{
a[j]=a[j-1];
j=j-1;
}
a[j]=index;
}
for(int j1=0;j1<a.length;j1++)
System.out.println(a[j1]);
}

}