SORTING

Merge sort using class template
Aim:
To write a C++ program for merge sort using template.
 Algorithm:
Step 1: Specify the template declaration and create a class as sort.
Step 2: Declare the data members as size and *v as template variable.
Step 3: Allocate the memory space using default constructor.
Step 4: Destroy the memory space using destructor.
Step 5: Declare the member functions as
void get()
void mergesort()
void merge()
void show()
Step 6: get() function is used to get the element.
Step 7: merge() sort function is used to divide the given element in equal parts .
Step 8: show() function is used to display the element.
Step 9: merge()  function is used to perform sort operation.
Step10: In the main, create the object using the following syntax:
  classname<datatype>object
Step11: Call the get() function, to input the elements.
Step12: Call the mergesort() and merge() function to perform divide and conquer
             operation.
Step13: Call the show function to display the sorted elements.

Program:
#include<iostream.h>
#include<conio.h>

template<class T>
class Sort
{
private:
int n,l,r;
T *Array;
T *b;
public:
Sort();
void get();
void callMerge();
void mergeSort(T a[],int l,int r);
void merge(T c[],T d[],int l,int m,int r);
void copy(T b[],T a[],int l,int r);
void show();
~Sort();
};

template <class T>
Sort<T>::Sort()
 {
cout<<"\nEnter the size of the array:";
cin>>n;
Array=new T[n];
b=new T[n];
            l=0;
            r=n-1;
}

template <class T>
void Sort<T>::get()
{
cout<<"\nEnter the Elements:\n";
for(int i=0;i<n;i++)
cin>>Array[i];
}

template <class T>
void Sort<T>::callMerge()
 {
(*this).mergeSort(Array,l,r);
}

template <class T>
void Sort<T>::mergeSort(T a[],int l,int r)
 {
if(l<r)
{
int i=(l+r)/2;
mergeSort(a,l,i);
mergeSort(a,i+1,r);
merge(a,b,l,i,r);
copy(b,a,l,r);
}

}

template <class T>
void Sort<T>::merge(T c[],T d[],int l,int m,int r)
{
int i=l,j=m+1,k=l;
while((i<=m) && (j<=r))
if(c[i]<=c[j])
d[k++]=c[i++];
else
d[k++]=c[j++];
if(i>m)
for(int q=j;q<=r;q++)
d[k++]=c[q];
else
for(int q=i;q<=m;q++)
d[k++]=c[q];
}

template <class T>
void Sort<T>::copy(T b[],T a[],int l,int r)
{
for(int i=l;i<=r;i++)
a[i]=b[i];
}

template <class T>
void Sort<T>::show()
{
cout<<"\nThe Elements in the Sorted Array:\t";
for(int i=0;i<n;i++,cout<<"\t")
cout<<Array[i];
}

template <class T>
Sort<T>::~Sort()
{
delete b;
delete Array;
}
void main()
{
clrscr();
cout<<"\n\t\t\t************\n";
cout<<"\n\t\t\tInteger Sort\n";
cout<<"\n\t\t\t************\n";
Sort<int> obj;
obj.get();
obj.callMerge();
obj.show();
cout<<"\n";
cout<<"\n\t\t\t**********\n";
cout<<"\n\t\t\tFloat Sort\n ";
cout<<"\n\t\t\t**********\n";
Sort<float> obj2;
obj2.get();
obj2.callMerge();
obj2.show();
cout<<"\n";
cout<<"\n\t\t\t************\n";
cout<<"\n\t\t\tCharater Sort\n ";
cout<<"\n\t\t\t************\n";
Sort<char> obj3;
obj3.get();
obj3.callMerge();
obj3.show();
getch();

}
       

Output:
  ************
   Integer Sort
 ************

Enter the size of the array:5

Enter the Elements:
23
11
1
67
2

The Elements in the Sorted Array:       1       2       11      23      67

                        **********
                       Float Sort
                      **********

Enter the size of the array:5

Enter the Elements:
2.3
1.1
6.7
4.5
9.9

The Elements in the Sorted Array:       1.1     2.3     4.5     6.7     9.9

                        ***********
                        Charater Sort
                        ***********

Enter the size of the array:5

Enter the Elements:
w
q
a
s
b

The Elements in the Sorted Array:       a       b       q       s       w


Ex.No.17
Quick sort using class template
Aim:
To write a C++ program for quick sort using template.
 Algorithm:
Step 1: Specify the template declaration and create a class as sort.
Step 2: Declare the data members n, lb and ub and *a as a template variable.
Step 3: Allocate the memory space using default constructor.
Step 4: Destroy the memory space using destructor.
Step 5: Declare the member functions as
void get()
void callquick()
void quick()
void show()
Step 6: get() function is used to get the element.
Step 7: callquick() function is used to call the quick function .
Step 8: quick() function is used to perform sort operation by using pivot element .
Step 9: In the main, create the object using the following syntax:
  classname<datatype>object
 Step10: Call the get() function, to input the elements.
Step11: Call the callquick() and quick() functions to perform sort operation.
Step12: Call the show() function to display the sorted elements.

Program:
#include<iostream.h>
#include<conio.h>
#include<process.h>

template<class T>
class Sort
{
private:
int n,lb,ub;
T *a;

public:
void get();
void callquick();
void quick(int lb,int ub);
void show();
~Sort();
};

template <class T>
void Sort<T>::get()
 {

cout<<"\nEnter the size of the array:";
cin>>n;
a=new T[n];
cout<<"\nEnter the Elements:";
for(int i=0;i<n;i++)
cin>>a[i];
lb=0;
ub=n-1;
}

template <class T>
void Sort<T>::callquick()
{
(*this).quick(lb,ub);
}

template <class T>
void Sort<T>::quick(int lb,int ub)
{
T temp=0;
T flag=1,i=0,j=0,key=0;
if(lb<ub)
{
i=lb;
j=ub+1;
key=a[lb];
while(flag==1)
{
i=i+1;
while(a[i]<key)
   i=i+1;
j=j-1;
while(a[j]>key)
  j=j-1;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
flag=0;
}
temp=a[lb];
a[lb]=a[j];a[j]=temp;
show();
quick(lb,j-1);
quick(j+1,ub);
}
}

template <class T>
void Sort<T>::show()
 {
cout<<"\nThe Elements in the Array:\t";
for(int i=0;i<n;i++,cout<<"\t")
cout<<a[i];
}

template <class T>
Sort<T>::~Sort()
{
delete a;
}

void main()
{
clrscr();
Sort<int>obj;
Sort<float>obj2;
Sort<char>obj3;
int w;
do
{
cout<<"\n\t\t***************\n";
cout<<"\n\t\t  QUICK SORT\n";
cout<<"\n\t\t***************\n";
cout<<"\n\t\t1.Integer Sort\n\t\t2.Float Sort\n\t\t3.Character Sort\n\t\t4.Exit\n";
cout<<"\n\t\tEnter Ur choice:";
cin>>w;
switch(w)
{
  case 1:
obj.get();
obj.callquick();
break;
    case 2:
obj2.get();
obj2.callquick();
break;
      case 3:
obj3.get();
obj3.callquick();
break;
      case 4:
 exit(0);
      }
      }while(w!=4);
getch();  
}

Output:

               ***************
                  QUICK SORT
                ***************

                1.Integer Sort
                2.Float Sort
                3.Character Sort
                4.Exit

                Enter Ur choice:1

Enter the size of the array:5

Enter the Elements:23 45 11 78 1

The Elements in the Array:      11      1       23      78      45
The Elements in the Array:      1       11      23      78      45
The Elements in the Array:      1       11      23      45      78

                ***************
                  QUICK SORT
                ***************

                1.Integer Sort
                2.Float Sort
                3.Character Sort
                4.Exit

                Enter Ur choice:3

Enter the size of the array:5

Enter the Elements:r s k a q

The Elements in the Array:      a       q       k       r       s
The Elements in the Array:      a       q       k       r       s
The Elements in the Array:      a       k       q       r       s

                 ***************
                  QUICK SORT
                ***************

                1.Integer Sort
                2.Float Sort
                3.Character Sort
                4.Exit

                Enter Ur choice:2

Enter the size of the array:5

Enter the Elements:2.2 4.5 1.1 7.8 0.1

The Elements in the Array:      1.1     0.1     2.2     7.8     4.5
The Elements in the Array:      0.1     1.1     2.2     7.8     4.5
The Elements in the Array:      0.1     1.1     2.2     4.5     7.8

                ***************
                  QUICK SORT
                ***************

                1.Integer Sort
                2.Float Sort
                3.Character Sort
                4.Exit

                Enter Ur choice:4