C++ program to sort an array of elements using Insertion Sort
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.
- Set A[0] : = -∞. [Initializes sentinel element]
-
Repeat steps 3 to 5 for K = 2,3, . . . . , N:
-
Set TEMP : = A[K] and PTR : = K-1.
-
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: Algorithms, Programs
