# Insertion Sort in C & C++ – Program & Algorithm

In this instructional exercise, I will clarify about calculation for insertion sort in C and C++ utilizing program model.

The insertion sort embeds every component in a legitimate spot. The technique behind the insertion sort is like the way toward sorting a pack of cards.

You can take a card, move it to its area in grouping and move the rest of the cards left or right as required.

In insertion sort, we accept that first component A in pass 1 is now sorted.

In pass 2 the following second component A is contrasted and the first and embedded into its legitimate spot either previously or after the principal component.

In pass 3 the third component A is embedded into its appropriate spot, etc.

The calculation for Insertion Sort in C and C++

Let ARR is a cluster with N components

Peruse ARR

Rehash stage 3 to 8 for I=1 to N-1

Set Temp=ARR[I]

Set J=I-1

Rehash stage 6 and 7 while Temp=0

Set ARR[J+1]=ARR[J] [Moves component forward]

Set J=J-1

[End of stage 5 internal

loop]

Set ARR[J+1]=Temp [Insert component inappropriate place]

[End of stage 2 external

loop]

Exit

Program for Insertion Sort in C

``````#include<stdio.h>

int main()
{
int i,j,n,temp,a;
printf("Enter the number of elements:");
scanf("%d",&n);
printf("\nEnter the elements\n");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;

while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];    //moves element forward
j=j-1;
}

a[j+1]=temp;    //insert element in proper place
}

printf("\nSorted list is as follows\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

return 0;
}``````

Program for Insertion Sort in C++

``````#include<iostream>

using namespace std;

int main()
{
int i,j,n,temp,a;
cout<<"Enter the number of elements:";
cin>>n;
cout<<"\nEnter the elements\n";

for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;

while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];    //moves element forward
j=j-1;
}

a[j+1]=temp;    //insert element in proper place
}

cout<<"\nSorted list is as follows\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}

return 0;
}``````

Output

Intricacy of Insertion Sort in C and C++

There is 1 examination during pass 1 for a legitimate spot. There are 2 correlations during pass 2 for the appropriate spot.

There are 3 examinations during pass 3 for legitimate spot, etc appropriately.

F(n) = 1 + 2 + 3 + . . . . + (n-1) = (n-1)/2 = O(n2)

Consequently unpredictability for insertion sort program in C and C++ is O(n2).

error: Alert: Content is protected!!