//優化的起泡排序類
#include "Sorter.h"

template <class Record,class Compare>
class ImprovedBubbleSorter:public Sorter<Record,Compare>
{
public:
	void Sort(Record Array[],int n);
};

//優化的起泡排序，Array[]為待排序數組，n為數組長度
template <class Record,class Compare>
void ImprovedBubbleSorter<Record,Compare>::Sort(Record Array[], int n) 
{ 
  bool NoSwap;			// 是否發生了交換的標志
  for (int i=1; i<n; i++)    {
    NoSwap = true;			// 標志初始為假
    for (int j=n-1; j>=i; j--)
      if (Compare::lt(Array[j], Array[j-1])) {
        swap(Array, j, j-1);	//如果發生了交換，標志為真
        NoSwap = false;
      }
    if (NoSwap)  // 如果沒發生過交換，表示已排好序，結束算法
      return;
    } 
}