//優化的快速排序類
#include "ImprovedInsertSorter.h"
#define THRESHOLD 16
template <class Record,class Compare>
class ImprovedQuickSorter:public Sorter<Record,Compare>
{
private:
	int SelectPivot(int left, int right);//選擇軸值，返回軸值下標
	int Partition(Record Array[], int left, int right);  //分割,返回軸值位置
	void DoSort(Record Array[],int left,int right);
public:
	void Sort(Record Array[],int left,int right);
};

//優化的快速排序，Array[]為待排序數組，i,j分別為數組兩端
template <class Record,class Compare>
void ImprovedQuickSorter<Record,Compare>::Sort(Record Array[], int left,int right) 
{
	//先對序列進行遞歸排序
	DoSort(Array,left,right);
	//最后對整個序列進行一次直接插入排序
	ImprovedInsertSorter<Record,Compare> insert_sorter;
	insert_sorter.Sort(Array,right-left+1);
}

template <class Record,class Compare>
void ImprovedQuickSorter<Record,Compare>::DoSort(Record Array[], int left,int right) 
{
    // 如果子序列中包含0或1個記錄，就不用排序
	if (right <= left) 
		return;    
	if (right-left+1 > THRESHOLD)
	{
		//選擇軸值
		//int pivot = SelectPivot(left, right);
		int pivot = (left+right)/2;
		// 將軸值放在數組末端
		swap(Array, pivot, right);   
		// 對剩余的記錄進行分割，分割后軸值已到達正確位置
		pivot = Partition(Array, left, right);
		//對分割出的子序列進行遞歸快速排序
		Sort(Array, left, pivot-1);  //對軸值左邊的子序列進行遞歸快速排序
		Sort(Array, pivot+1, right); //對軸值右邊的子序列進行遞歸快速排序
	}
}

//選擇軸值
template <class Record,class Compare>
int ImprovedQuickSorter<Record,Compare>::SelectPivot(int left,int right) 
{   //參數left,right分別表示序列的左右端下標
   //選擇中間紀錄作為軸值
	return (left+right)/2; 
}

//分割
template <class Record,class Compare>
int ImprovedQuickSorter<Record,Compare>::Partition(Record Array[], int left,int right) 
{
	Record TempRecord;		//存放軸值的臨時變量
    int i = left;				// i為左指針，j為右指針
	int j = right;	
    TempRecord = Array[j];	//將軸值存放在臨時變量中
    while (i != j)  {	//開始進行分割，i,j開始向中間移動，直到相遇
       //i指針向右移動，直到找到一個大于等于軸值的記錄
       while (Compare::lt(Array[i], TempRecord) && (j>i))
		   i++;
       // 如果i,j尚未相遇，就將逆序元素換到右邊的空閑位置
       if (i<j)
       {  
			Array[j] = Array[i];   
			j--;	//j指針向左移動一步
       }
       // j指針向左移動，直到找到一個小于等于軸值的記錄
       while (Compare::gt(Array[j], TempRecord) && (j > i))  j--;
       //如果i,j尚未相遇，就將逆序元素換到左邊的空閑位置
       if (i<j)
		{
			  Array[i] = Array[j];
			  i++;	//i指針向右移動一步
		}
    }	//end while
    Array[i] = TempRecord;	//把軸值回填到分界位置i上
	return i;	//返回分界位置i
}