Insertion Sort

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
    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

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

Insertion sort in linklist

#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;
}
};
class linklist
{
node*head;
int count;

public:
linklist()
{
head=NULL;
count=0;
}

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

}

void display()
{
node*p;
p=head;

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

void insort()
{
int tmp=0;

node*p=head->next,*q=head,*r,*s;
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;
p=head;
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));
linklist a;
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();
}

Related links 

Single link list                 Stack              AVL Trees             Binary search          Counting Sort

Doubly link list               Queue              Graphs                  Bubble Sort               Radix sort

Circular link list              Binary search tree       Hashing         Insertion Sort         Bucket Sort

Josephus Problem          Tree Traversal              Heaps                Quick Sort              Merge Sort

 

At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses

 

Search within CuiTutorial

Scroll to Top