//Shell排序類
#include "Sorter.h"

template <class Record,class Compare>
class ShellSorter:public Sorter<Record,Compare>
{
private:
	// 針對變化的增量而修改的插入排序算法，參數delta表示當前的增量
	void ModifiedInsertSort(Record Array[],int n,int delta);
public:
	void Sort(Record Array[],int n);
	void delta3Sort(Record Array[], int n);
};

//Shell排序，Array[]為待排序數組，n為數組長度
template <class Record,class Compare>
void ShellSorter<Record,Compare>::Sort(Record Array[], int n) 
{ 
	for (int delta=n/2; delta>0; delta/=2)      //增量delta每次除以2遞減
		for (int j=0; j<delta; j++)       //分別對delta個子序列進行插入排序
			ModifiedInsertSort(&Array[j], n-j, delta);
}

//Shell排序，Array[]為待排序數組，n為數組長度
template <class Record,class int_intCompare>
void ShellSorter<Record,int_intCompare>::delta3Sort(Record Array[], int n) 
{ 
	for (int delta=n/3; delta>=3; delta/=3)      //增量delta每次除以3遞減
		for (int j=0; j<delta; j++)       //分別對delta個子序列進行插入排序
			ModifiedInsertSort(&Array[j],n-j, delta);
	ModifiedInsertSort(Array,n,1);
}

// 針對變化的增量而修改的插入排序算法，參數delta表示當前的增量
template <class Record,class Compare>
void ShellSorter<Record,Compare>::ModifiedInsertSort(Record Array[],int n, int delta) 
{
	for (int i=delta; i<n; i+=delta) // 對子序列中第i個記錄排序
		for (int j=i; (j>=delta)&&(Compare::lt(Array[j], Array[j-delta])); j-=delta)
		{
//			if 
				swap(Array, j, j-delta);
//			else break;
		}
}