/* 3. Write a C++ program to create a template function for quick sort and demonstrate sorting of integers and double data types. */

#include<iostream.h>
#include<conio.h>
template<class T>
int partition(T a[],int low,int high)
{
    int i,j;
    T key,temp;
    key=a[low];
    i=low+1;
    j=high;
    while(1)
    {
        while (key >= a[i]) i++;
        while (key < a[j]) j--;
        if (i < j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
        else
        {
            temp=a[low];
            a[low]=a[j];
            a[j]=temp;
            return j;
        }
    }
}
template<class T>
T qsort(T &a,int low,int high)
{
    int j;
    if (low < high)
    {
        j=partition(a,low,high);
        qsort(a,low,j-1);
        qsort(a,j+1,high);
    }
}
void main()
{
    double *a;
    int n,i;
    clrscr();
    cout<<"\nEnter the size of the array : ";
    cin>>n;
    a = new double[n];
    cout<<"\nEnter the elements of the array :\n";
    for (i=0; i<n; i++)
        cin>>a[i];
    cout<<"\nUnsorted elements are :\n";
    for (i=0; i<n; i++)
        cout<<a[i]<<"\n";
    qsort(a,0,n-1);
    cout<<"\nSorted elements are as follows :\n";
    for (i=0; i<n; i++)
        cout<<a[i]<<"\n";
    getch();
}