Insertion Sort Time complexity Analysis 

On the ith pass we “insert” the ith element A[i] into its rightful place among A[1],A[2],…A[i-1] which were placed in sorted order.

After this insertion A[1],A[2],…A[i] are in sorted order.

• Time taken by Insertion Sort depends on input
• Can take different amounts of time to sort 2 input sequences of the same size
• In general, the time taken by an algorithm grows with the size of the input

Strategy

• Start “empty handed”
• Insert a card in the right position of the already sorted hand
• Continue until all cards are inserted/sorted

Analysis of Insertion sort Algorithms

Efficiency:

• Running time
• Space used

int j;

for int p=1; p< size (A); p++

{

 int temp = A[p];

for (j=p;j>0 && temp< a[j-1]; j–)

  A[j]=A[j-1];

A[j]=temp;

}

• Number of comparison in the inner loop is dependent on value of p
• Summing all step gives

Best/Worst/Average Case

Best case: elements already sorted ® running time = O(N), i.e., linear time.

• the inner loop always fails immediately

Worst case: elements are sorted in inverse order ® running time = O(n2), i.e., quadratic time

• Because inner loop runs p time

Average case: half of the elements are sorted

• running time = O(n2),
• Inner loop runs p/2 times

C++ code for insertion sort using loop

#include<iostream>
#include<conio.h>

using namespace std;
void insertsort(int arry[],int n)
{
for(int wall=1; wall<n; wall++)
{
for(int i=wall; i>0; i–)
{
if(arry[i]<arry[i-1])
{ int y;
y=arry[i];
arry[i]=arry[i-1];
arry[i-1]=y;
}
else
break;
}

}
}

void main()
{

int n=10;

int arry[10];
for(int j=0; j<n; j++)
{cout<<“enter ur num at index “<<j<<” = “;
cin>>arry[j];

}
cout<<“after inseration sort “<<endl<<endl;

insertsort(arry,n);

for(int i=0; i<n; i++)
{
cout<<“ur sorted arry is “<<arry[i]<<endl;
}

getch();
}