In C++, you can create your own header file and declare function prototypes in them. An then you can define the functions in .cpp file.
In this post, I will demonstrate how to implement some the most common sorting algorithms in C++ using a custom made header file.
In this post, I will demonstrate how to implement some the most common sorting algorithms in C++ using a custom made header file.
// sort.h
#ifndef SORT_H_
#define SORT_H_
#define n 10
class sort
{
private:
int a[n];
public:
void display();
void input();
void bubble_sort();
void selection_sort();
void insertion_sort();
void merge_sort(int[],int,int);
void quick_sort(int[],int,int);
void shell_sort();
void radix_sort();
};
#endif
// sort.cpp
#include<iostream>
#include "sort.h"
#include<malloc.h>
#include<stdlib.h>
using namespace std;
int b[n];
void sort::input()
{
int i;
for(i=0;i<n;i++)
a[i]=rand()%100;
}
void recur_input()
{
int i;
for(i=0;i<n;i++)
b[i]=rand()%100;
}
void sort::display()
{
int i;
for(i=0;i<n;i++)
cout<<a[i]<<" ";
}
void recur_display()
{
int i;
for(i=0;i<n;i++)
cout<<b[i]<<" ";
}
void merge(int a[],int l,int mid,int h)
{
int i=l,j=mid+1,k=l,c[50];
while((i<=mid)&&(j<=h))
{
if(a[i]<=a[j])
c[k++]=a[i++];
else
c[k++]=a[j++];
}
while(i<=mid)
c[k++]=a[i++];
while(j<=h)
c[k++]=a[j++];
for(i=l;i<k;i++)
a[i]=c[i];
}
int partition(int *a,int l,int h)
{
int i,j,pv;
pv=a[l];
i=l,j=h+1;
do
{
while(a[i]<=pv) i++;
while(a[j]>pv) j--;
if(i<j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else break;
}while(i<=j);
int temp=a[l];
a[l]=a[i-1];
a[i-1]=temp;
return i-1;
}
void sort::bubble_sort()
{
int i,j;
for(i=0;i<n-1;i++)
for(j=0;j<n-1-i;j++)
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
void sort::selection_sort()
{
int i,j,min,pos;
for(i=0;i<n;i++)
{
min=a[i];
pos=i;
for(j=i+1;j<n;j++)
{
if(a[j]<min)
{
min=a[j];
pos=j;
}
}
if(pos!=i)
{
int temp=a[i];
a[i]=a[pos];
a[pos]=temp;
}
}
}
void sort::insertion_sort()
{
int temp,i,j;
for(i=1;i<n;i++)
{
temp=a[i];
for(j=i-1;((j>=0)&&(temp<a[j]));j--)
{
a[j+1]=a[j];
}
a[j+1]=temp;
}
}
void sort::merge_sort(int a[],int l,int h)
{
int mid;
if(l<h)
{ mid=(l+h)/2;
merge_sort(a,l,mid);
merge_sort(a,mid+1,h);
merge(a,l,mid,h);
}
}
void sort::quick_sort(int a[],int l,int h)
{
int x;
if(l>=h) return;
x=partition(a,l,h);
quick_sort(a,l,x-1);
quick_sort(a,x+1,h);
}
void sort::shell_sort()
{
int i,j,d=n*4/5;
while(d>=1)
{
for(i=0;i<n-d;i++)
if(a[i]>a[i+d])
{
int temp=a[i];
a[i]=a[i+d];
a[i+d]=temp;
}
if(d==1)
break;
d=d*4/5;
}
}
void sort::radix_sort()
{
int i,j,k=1,l,temp,b[10][n],cnt;
int max=a[0],c=0;
for(i=0;i<n;i++)
if(a[i]>max)
max=a[i];
while(max%10)
{
c++;
max/=10;
}
for(i=0;i<10;i++)
for(j=0;j<n;j++)
b[i][j]=-999;
for(l=0;l<c;l++)
{
for(j=0;j<n;j++)
{
temp=(a[j]/k)%10;
b[temp][j]=a[j];
}
k=k*10; cnt=0;
for(i=0;i<10;i++)
for(j=0;j<n;j++)
if(b[i][j]!=-999)
a[cnt++]=b[i][j];
for(i=0;i<10;i++)
for(j=0;j<n;j++)
b[i][j]=-999;
}
}
main()
{
int ch,i;
cout<<"\nProgram of sorting algorithms :\n";
sort s;
do
{
cout<<"\n\n[1] Bubble [2] Selection [3] Insertion ";
cout<<"\n[4] Merge [5] Quick [6] Shell Sort ";
cout<<"\n[7] Radix [8] Exit ";
cout<<"\nEnter your choice : ";
cin>>ch;
switch(ch)
{
case 1:
s.input();
cout<<"\nArray before sorting : \n";
s.display();
s.bubble_sort();
cout<<"\nArray after sorting : \n";
s.display();
break;
case 2:
s.input();
cout<<"\nArray before sorting : \n";
s.display();
s.selection_sort();
cout<<"\nArray after sorting : \n";
s.display();
break;
case 3:
s.input();
cout<<"\nArray before sorting : \n";
s.display();
s.insertion_sort();
cout<<"\nArray after sorting : \n";
s.display();
break;
case 4:
recur_input();
cout<<"\nArray before sorting : \n";
recur_display();
s.merge_sort(b,0,n-1);
cout<<"\nArray after sorting : \n";
recur_display();
break;
case 5:
recur_input();
cout<<"\nArray before sorting : \n";
recur_display();
s.quick_sort(b,0,n-1);
cout<<"\nArray after sorting : \n";
recur_display();
break;
case 6:
s.input();
cout<<"\nArray before sorting : \n";
s.display();
s.shell_sort();
cout<<"\nArray after sorting : \n";
s.display();
break;
case 7:
s.input();
cout<<"\nArray before sorting : \n";
s.display();
s.radix_sort();
cout<<"\nArray after sorting : \n";
s.display();
break;
case 8:
break;
default: cout<<"\nEnter correct choice .... \n";
break;
}
}while(ch!=8);
}
