MERGE SORT USING TEMPLATES

MERGE SORT USING TEMPLATES

AIM:

            To write a program to implement merge sort using templates.

ALGORITHM:

Step 1: Start the process.

Step 2: Get the number of elements to be sorted.

Step 3: At every pass, one element is placed in the correct position.

Step 4: The initially sorted position is null and the complete list is unsorted with every pass, the sorted portion grows by one element and the unsorted portion shrinks by one element.

Step 5: If the interchange has occurred then the current position of the data will be moved.

Step 6: The passes can be stopped if there is no interchange in the current pass. No interchange indicates that the elements are sorted.

Step 7: Stop the process.

PROGRAM:

#include<iostream.h>

#include<conio.h>

#include<iomanip.h>

template<class t>

class sort

{

t a[10];

public:

void get(int);

void merge(int,int);

void mergesort(int,int,int);

void display(int);

};

template<class t>

void sort<t>::get(int n)

{

int i;

cout<<"\n\n Enter the Array Elements:";

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

cin>>a[i];

}

template<class t>

void sort<t>::display(int n)

{

int i;

cout<<"\n The Sorted Array is\n";

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

cout<<a[i]<<setw(5);

}

template<class t>

void sort<t>::merge(int low,int high)

{

int mid;

if(low<high)

{

mid=(low+high)/2;

merge(low,mid);

merge(mid+1,high);

mergesort(low,mid,high);

}

}

template<class t>

void sort<t>::mergesort(int low,int mid,int high)

{

t b[10];

int h,i,j,k;

h=low;

i=low;

j=mid+1;

while((h<=mid)&&(j<=high))

{

if(a[h]<=a[j])

{

b[i]=a[h];

h=h+1;

}

else

{

b[i]=a[j];

j=j+1;

}

i=i+1;

}

if(h>mid)

{

for(k=j;k<=high;k++)

{

b[i]=a[k];

i=i+1;

}

}

else

{

for(k=h;k<=mid;k++)

{

b[i]=a[k];

i=i+1;

}

}

for(k=low;k<=high;k++)

a[k]=b[k];

}

void main()

{

int n;

clrscr();

cout<<"\n\t\t Merge Sort Using Templates";

cout<<"\n\t\t~~~~~~~~~~~~~~~~~~~~~";

sort<int>n1;

sort<float>n2;

cout<<"\n Enter the Array Size:";

cin>>n;

cout<<"\n----Integer values----\n";

n1.get(n);

n1.merge(1,n);

n1.display(n);

cout<<"\n\n----Float values----\n";

n2.get(n);

n2.merge(1,n);

n2.display(n);

getch();

}

OUTPUT:

                 Merge Sort Using Templates

                ~~~~~~~~~~~~~~~~~~~~~

 Enter the Array Size:5

----Integer values----

 Enter the Array Elements:12 45 23 10 78

 The Sorted Array is 10   12   23   45   78

----Float values----

 Enter the Array Elements:12.4 34.6 67.8 13.9 33.2

 The Sorted Array is 12.4  13.9 33.2 34.59 67.8

RESULT:

Thus the program to implement Merge Sort using Templates was executed.