# Insertion Sort using loop and recursive function complete code

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

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;

}

Strategy

• Start “empty handed”
• Insert a card in the right
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

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;

}

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

• Because inner loop runs p time

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;

}

Average case: half of the elements are sorted

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

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;

}

# 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();
}

# C++ code for insertion sort using recursive function

#include <iostream>

using namespace std;

void insertionSort(int a[], int length, int round = 1);

int _tmain(int argc, _TCHAR* argv[])
{
cout<<“Insertion sort \n”;
cout<<“Enter mumber of elements : “;
int n,a[20];
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
insertionSort(a,n);
cout<<“\n===============\n”;
for(int i=0;i<n;i++){
cout<<a[i]<<” “;
}
cout<<“\n===============\n”;
write system pause command here
return 0;
}

void insertionSort(int a[],int length,int round){
if(round < length)
{
int key = a[round];
int j;
for (j = round-1 ; j>=0 && a[j]>key;j–)
a[j+1] = a[j];
a[j+1]=key;
round+=1;
insertionSort(a,length,round);
}
}

#include<iostream>
#include<conio.h>
#include<cstdlib>
#include<time.h>
#include<windows.h>

using namespace std;

class node
{
public:
int data;
node*next;
node*pre;
node()
{
next=NULL;
pre=NULL;
data=0;
}
};
{
int count;

public:
{
count=0;
}

void insert(int dataa)
{
node*newnode=new node;
newnode->data=dataa;
newnode->next=p;
if(p!=NULL)
p->pre=newnode;
count++;

}

void display()
{
node*p;

while(p!=NULL)
{
cout<<p->data<<” “;
if(p->next==NULL)
break;
p=p->next;
}
}

void insort()
{
int tmp=0;

r=p;s=q;
for(int i=1;i<count&&p!=NULL;i++)
{
for(int j=i;j>=0&&q!=NULL;j–)
{
if(p->data<q->data)
{
tmp=p->data;
p->data=q->data;
q->data=tmp;
}

p=q;
q=q->pre;
}
s=r;
r=r->next;
p=r;
q=s;

}
}

node* binary_search(int dataa,int left,int right)
{
node*p;
int mid=(left+right)/2;
for(int i=1;i<mid;i++)
p=p->next;

if(p->data==dataa)
return p;

if(left-right==0)
return NULL;

if(dataa<p->data)
return binary_search(dataa,left,mid);
else
return binary_search(dataa,mid+1,right);
}

int getcount()
{return count;}

};

int main()
{
srand(time(0));
for(int i=1;i<=10;i++)
a.insert(rand()%100);
a.display();
cout<<endl;
a.insort();
a.display();
int data;
cout<<endl<<“Enter data: “;
cin>>data;
node*p=a.binary_search(data,1,a.getcount());
if(p!=NULL)
cout<<p->data<<” “<<p;
else
cout<<p<<“NO DATA EXISTS”;

getch();
}