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.