#include "QuickSort.h"


template<class T>
int Partition1(T a[],int p,int r)
{
int i=p,j=r+1;
T x=a[p];
while(true)

{
while(a[++i]<x);
while(a[--j]>x);
if(i>=j)break;
Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}

template<class T>
int Partition(T a[],int low,int high)
{
	T temp=a[low];;
	int i,j;
	i=low+1;
	j=high;
	while(i<j)
	{
		while(i<=j && a[i]<temp)
		  i++;
		while(i<=j && a[j]>temp)
		  j--;
		if(i<j)
	  	Swap(a[i],a[j]);
	} 
	a[low]=a[j];
	a[j]=temp;
	return j;	
} 

template<class T>
void Swap(T &a,T &b)
{
	T temp;
	temp=a;
	a=b;
	b=temp;
}

template<class T>
void QuickSort(T a[],int low,int high)
{
	int j;
	if (low<high)
	{
		j= Partition(a,low,high);
		QuickSort(a,low,j-1);
		QuickSort(a,j+1,high);
	}
}