QuickSort Randomised with hoares partition and simple partition

quicksort.cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;

typedef long long ll;


template <class T>
void swap(T *a,T *b)
{
    T temp=*a;
    *a=*b;
    *b=temp;

}
template <class T>
ll qpartition(T a[],ll low,ll high)
{
    T x=a[high];
    ll i=low-1;
    for(ll j=low;j<=high-1;j++)
    {
        if(a[j]<=x) // that is smaller than x (right element we just swap it with the wrong element we hv marked with i)
        {
            i=i+1;
            swap(&a[i],&a[j]);
        }
    }
    //move pivot to its proper position
    swap<T> (&a[i+1],&a[high]);
    return i+1;

}

template <class T>
ll hpartition(T a[],ll low,ll high)
{
    T x=a[low];
    ll i=low+1;
    ll j=high;
    while(i<=j)
    {
        while(a[j]>x)
            j--;

        while(a[i]<x)
            i++;

        if(i<j)
            swap<T> (&a[i],&a[j]);

    }
    swap<T> (&a[low],&a[j]);
    return j;
}



template <class T>
void quicksort(T a[],ll low,ll high)
{
    if (low<high)
    {
        //could use either
        //ll pivot=qpartition<T> (a,low,high);
        ll pivot=hpartition<T> (a,low,high);
        quicksort(a,low,pivot-1);
        quicksort(a,pivot+1,high);
    }
}



template <class T>
ll randpartition(T a[],ll low,ll high)
{
    ll x=low+rand()%(high-low+1);
//    swap(&a[x],&a[high]);//for qpartition
//    return qpartition<T> (a,low,high);

    swap<T> (&a[x],&a[low]);//for hpartition
    return hpartition<T> (a,low,high);


}

template <class T>
void randquicksort(T a[],ll low,ll high)
{
    if (low<high)
    {
        //could use either
        //ll pivot=qpartition<T> (a,low,high);
        ll pivot=randpartition<T> (a,low,high);
        randquicksort(a,low,pivot-1);
        randquicksort(a,pivot+1,high);
    }
}





int main()
{
    float a[100];
    for(int i=1;i<=5;i++)
        cin>>a[i];

    randquicksort<float>(a,1,5);

    for(int i=1;i<=5;i++)
        cout<<a[i]<<"   ";
}