Insertion Sort

Insertion Sort:

In most cases the insertion sort is the best of the elementary sorts.It still executes in O(N^2) time but its twice as fast as the bubble sort and somewhat faster than Selection Sort in normal situation.

Insertion Sort Workspace:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
class ArrayIns
{
 private long[] array;
 private int nElems;

 public ArrayIns(int max)
 {
array=new long[max];
nElems=0;
 }

 public void insert(long value)
 {
 array[nElems]=value;
 nElems++;
 }

 public void display()
 {
 for(int j=0;j<nElems;j++)
 System.out.println(array[j] + " ");
 System.out.println(" ");
 }


 public void insertionSort()
 {
int in,out;
for(out=1;out<nElems;out++)
{
long temp=array[out];
in=out;
while(in>0 && array[in-1]>=temp)
{
array[in] =array[in-1];
--in;
}
array[in] =temp;
}
 }

}



public class InsertionSortTest {

/**
*
*/
public InsertionSortTest() {
// TODO Auto-generated constructor stub
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

ArrayIns arr=new ArrayIns(100);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.display();
arr.insertionSort();
arr.display();

}


}

Efficiency of Insertion Sort:

So on the first pass ,it compares a maximum of one item.On the second pass,its a maximum of two items are actually compared before the insertion point is found,we can divide by 2 which gives N*(N-1)/4 .The number of copies is approximately same as the number of comparisons.

So ,Insertion Sort runs in O(N^2) time.