# C++ program to sort an array of elements using Insertion Sort

19-06-2016

Aim:

To write a program to an array of elements using insertion sort technique.

Algorithm:

INSERTION ( A, N)

This algorithm sorts an array A with N elements.

1.   Set A[0] : = -∞. [Initializes sentinel element]

2.   Repeat steps 3 to 5 for K = 2,3, . . . . , N:

3.    Set TEMP : = A[K] and PTR : = K-1.

4.   Repeat while TEMP<A[PTR]:

(a) Set A[PTR+1] : = A[PTR]. [Moves element forward.]

(b) Set PTR : = PTR – 1.

[End of loop]

5.   Set A[PTR+1] : = TEMP. [Inserts element in proper place.]

[End of step 2 loop.]

6. Return.

Program code:

```#include<iostream.h>

#include<conio.h>

#include<process.h>

class insertion

{

int i,n,a[20];

public:

void insert()

{

cout<<"Enter the array length : ";

cin>>n;

cout<<"Enter the elements : ";

for(i=1;i<=n;i++)

{

cin>>a[i];

}
}

void sort()

{

int t,k,p;

a[0]=-100;
for(k=2;k<=n;k++)

{

t=a[k];
p=k-1;
while(t<a[p])
{
a[p+1]=a[p];
p=p-1;
}
a[p+1]=t;
}
)
void display()

{

cout<<"\nSorted array is \n":

for(i=1;i<=n;i++)
cout<<" "<<a[i];

}

};

void main()

{

clrscr();

insertion s;

s.insert();

s.sort();

s.display();

getch();

}```

Output:

Enter the array length : 6

Enter the elements : 1 8 3 7 2 6

Sorted array is

1 2 3 6 7 8

Tagged in: ,