#ifndef SORT_CLASS
#define SORT_CLASS

#include "SeqList.h"

#include <stdlib.h>

template <class T>
class Sort
{
public:
	Sort(){}
	~Sort(){}
	void InsertionSort(SeqList<T> & list);
	void Insert(SeqList<T> & list,int i);
	void BinaryInsertSort(SeqList<T> &list);
	void BinaryInsert(SeqList<T> & list,int i);
	void ShellSort(SeqList<T> & list);
	void ShellInsert(SeqList<T> & list,const int gap);
	void BubbleSort(SeqList<T> & list);
	void BubbleExchange(SeqList<T> & list,const int i,int & exchange);
	void QuickSort(SeqList<T> & list,const int left,const int right);
	int Partition(SeqList<T> & list,const int low,const int high);
	void SelectSort(SeqList<T> & list);
	void SelectExchange(SeqList<T> & list,const int i);
	void HeapSort(SeqList<T> & list);
	void FilterDown(SeqList<T> & list,const int i,const int EndOfHeap);
};

template <class T>
void Sort<T>::InsertionSort(SeqList<T> & list)
{
	for(int i=1;i<=list.currPos;i++)
		Insert(list,i);
}

template <class T>
void Sort<T>::Insert(SeqList<T> & list,int i)
{
	T temp=list.dataList[i];
	int j=i;
	while(j>0&&temp<list.dataList[j-1])
	{
		list.dataList[j]=list.dataList[j-1];
		j--;
	}
	list.dataList[j]=temp;
}

template <class T>
void Sort<T>::BinaryInsertSort(SeqList<T> & list)
{
	for(int i=1;i<=list.currPos;i++)
		BinaryInsert(list,i);
}

template <class T>
void Sort<T>::BinaryInsert(SeqList<T> & list,int i)
{
	int left=0,right=i-1;
	T temp=list.dataList[i];
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(temp<list.dataList[middle])
			right=middle-1;
		else
			left=middle+1;
	}
	for(int k=i-1;k>=left;k--)
		list.dataList[k+1]=list.dataList[k];
	list.dataList[left]=temp;
}

template <class T>
void Sort<T>::ShellSort(SeqList<T> & list)
{
	int gap=(list.currPos+1)/2;
	while(gap)
	{
		ShellInsert(list,gap);
		gap=gap==2?1:(int)(gap/2);
	}
}

template <class T>
void Sort<T>::ShellInsert(SeqList<T> &list,const int gap)
{
	for(int i=gap;i<=list.currPos;i++)
	{
		T temp=list.dataList[i];
		int j=i;
		while(j>=gap&&temp<list.dataList[j-gap])
		{
			list.dataList[j]=list.dataList[j-gap];
			j-=gap;
		}
		list.dataList[j]=temp;
	}
}

template <class T>
void Sort<T>::BubbleSort(SeqList<T> & list)
{
	int pass=1;
	int exchange=1;
	while(pass<=list.currPos&&exchange)
	{
		BubbleExchange(list,pass,exchange);
		pass++;
	}
}

template <class T>
void Sort<T>::BubbleExchange(SeqList<T> & list,const int i,int & exchange)
{
	exchange=0;
	for(int j=list.currPos;j>=i;j--)
		if(list.dataList[j-1]>list.dataList[j])
		{
			T temp=list.dataList[j];
			list.dataList[j]=list.dataList[j-1];
			list.dataList[j-1]=temp;
			exchange=1;
		}
}

template <class T>
void Sort<T>::QuickSort(SeqList<T> & list,const int left,const int right)
{
	if(left<right)
	{
		int pivotpos=Partition(list,left,right);
		QuickSort(list,left,pivotpos-1);
		QuickSort(list,pivotpos+1,right);
	}
}

template <class T>
int Sort<T>::Partition(SeqList<T> & list,const int low,const int high)
{
	int pivotpos=low;
	T pivot=list.dataList[low];
	for(int i=low+1;i<=high;i++)
	{
		if(list.dataList[i]<pivot&&++pivotpos!=i)
		{
			T temp=list.dataList[i];
			list.dataList[i]=list.dataList[pivotpos];
			list.dataList[pivotpos]=temp;
		}
	}
	T temp=list.dataList[low];
	list.dataList[low]=list.dataList[pivotpos];
	list.dataList[pivotpos]=temp;
	return pivotpos;
}

template <class T>
void Sort<T>::SelectSort(SeqList<T> & list)
{
	for(int i=0;i<list.currPos;i++)
		SelectExchange(list,i);
}

template <class T>
void Sort<T>::SelectExchange(SeqList<T> & list,const int i)
{
	int k=i;
	for(int j=i+1;j<=list.currPos;j++)
	{
		if(list.dataList[j]<list.dataList[k])
			k=j;
		if(k!=i)
		{	
			T temp=list.dataList[i];
			list.dataList[i]=list.dataList[k];
			list.dataList[k]=temp;
		}
	}
}

template <class T>
void Sort<T>::HeapSort(SeqList<T> & list)
{
	for(int i=(list.currPos-1)/2;i>=0;i--)
		FilterDown(list,i,list.currPos);
	for(i=list.currPos;i>=1;i--)
	{
		T temp=list.dataList[i];
		list.dataList[i]=list.dataList[0];
		list.dataList[0]=temp;
		FilterDown(list,0,i-1);
	}
}

template <class T>
void Sort<T>::FilterDown(SeqList<T> & list,const int i,const int EndOfHeap)
{
	int current=i;
	int child=2*i+1;
	T temp=list.dataList[i];
	while(child<=EndOfHeap)
	{
		if(child<EndOfHeap&&list.dataList[child]<list.dataList[child+1])
			child++;
		if(temp>list.dataList[child]) break;
		else
		{
			list.dataList[current]=list.dataList[child];
			current=child;
			child=2*child+1;
		}
	}
	list.dataList[current]=temp;
}



#endif