//9_13.h
#ifndef ARRAY_BASED_SORTING_FUNCTIONS
#define ARRAY_BASED_SORTING_FUNCTIONS

// 輔助函數：交換x和y的值
template <class T>
void Swap (T &x, T &y)
{
   T temp;
   
   temp = x;
   x = y;
   y = temp;
}

// 用起泡法對數組A的n個元素進行排序
template <class T>
void BubbleSort(T A[], int n)
{
   int i,j;             
   int lastExchangeIndex;	//用于記錄每趟被交換的最后一對元素中較小的下標
   i = n-1;	// i是下一趟需參與排序交換的元素之最大下標
   while (i > 0)        //持續排序過程，直到最后一趟排序沒有交換發生，或已達n-1趟
   {
      lastExchangeIndex = 0;	//每一趟開始時，設置交換標志為0（未交換）
      for (j = 0; j < i; j++)	//每一趟對元素A[0]..A[i]進行比較和交換
         if (A[j+1] < A[j])	//如果元素A[j+1] < A[j]，交換之
         { 
            Swap(A[j],A[j+1]);
            lastExchangeIndex = j;	//記錄被交換的一對元素中較小的下標
         }
      i = lastExchangeIndex;       // 將i設置為本趟被交換的最后一對元素中較小的下標
   }
}
#endif