Ex. No 6 Generating Templates for standard sorting
algorithms
Aim
To write a C++ program to implement the Templates of standard sorting
algorithms such as bubble sort, insertion sort, merge sort, and quick sort
Algorithm
Step 1: Start the Process.
Step 2: Create the template to handle bubble sort, insertion sort, and
quick sort, merge sort.
Step 3: Get the element using for loop.
Step 4: Call the template function for sorting.
Step 5: Display the result.
Step 6: Stop the process.
Program
#include<iostream.h>
#include<conio.h>
int a[20];
enum Boolean{false,true};
void merge(int,int,int);
//Bubble Sort
template<class T>
void swap(T &x,T&y)
{
T t;
t=x;
x=y;
y=t;
}
template<class T>
void bubb(T &s,int size)
{
Boolean swapped=true;
for(int i=0;(i<size-1)&swapped;i++)
{
swapped=false;
for(int j=0;j<(size-1)-i;j++)
if(s[j]>s[j+1])
{
swapped=true;
swap(s[j],s[j+1]);
}
}
}
//Merge Sort
Template<class T>
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
}
//Insertion Sort
template<class T>
void insertionsort(T numbers[], int array_size)
{
T i, j, index;
for (i=1; i < array_size; i++)
{
index = numbers[i];
j = i;
while ((j > 0) & (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}
//Quick Sort
template<class T>
int Partition(int low,int high,T arr[])
{ T pivot,high_vac,low_vac;
pivot=arr[low];
while(high>low)
{
high_vac=arr[high];
while(pivot<high_vac)
{
if(high<=low) break;
high--;
high_vac=arr[high];
}
arr[low]=high_vac;
low_vac=arr[low];
while(pivot>low_vac)
{
if(high<=low)
break;
low++;
low_vac=arr[low];
}
arr[high]=low_vac;
}
arr[low]=pivot;
return low;
}
template<class T>
void Quick_sort(int low,int high,T arr[])
{
int Piv_index;
if(low<high)
{
Piv_index=Partition(low,high,arr);
Quick_sort(low,Piv_index-1,arr);
Quick_sort(Piv_index+1,high,arr);
}
}
void main()
{
int num[25],temp[25];
float floatnum[25];
int i,size,ch;
clrscr();
cout<"Program to sort.."<endl;
cout<"enter the size of interger and float:";
cin>size;
cout<"Enter the integer element"<endl;
for(i=0;i<size;i++)
cin>num[i];
cout<"Enter the float element"<endl;
for( i=0;i<size;i++)
cin>floatnum[i];
do
{
cout<"Sorting"<endl;
cout<"1.Merge Sort\n2.Quick sort\n3.Insertion sort\n4.Bubble
sort\n5.Float bubble sort\n6.Float insertion sort\n7.Float quick
sort\n8.Exit"<endl;
cout<"Enter your choice:";
cin>ch;
switch(ch)
{
case 1:
merge_sort(0,size);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<num[i]<"\n";
break;
case 2:
Quick_sort(0,size-1,num);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<num[i]<"\n";
break;
case 3:
insertionsort(num,size);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<num[i]<"\n";
break;
case 4:
bubb(num,size);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<num[i]<"\n";
break;
case 5:
bubb(floatnum,size);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<floatnum[i]<"\n";
break;
case 6:
insertionsort(floatnum,size);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<floatnum[i]<"\n";
break;
case 7:
Quick_sort(0,size-1,floatnum);
cout<"sorted vector:"<endl;
for(i=0;i<size;i++)
cout<floatnum[i]<"\n";
break;
case 8:
break;
}
}while(ch<8);
Getch();
}