#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 SelectionSort(T A[], int n)
{
   int smallIndex;    //每以趟中選出的最小元素之下標
   int i, j;

   // sort A[0]..A[n-2], and A[n-1] is in place
   for (i = 0; i < n-1; i++) 
   {
      smallIndex = i;    //最小元素之下標初值設為i
      // 在元素A[i+1]..A[n-1]中逐個比較顯出最小值
      for (j = i+1; j < n; j++) 
         // smallIndex始終記錄當前找到的最小值的下標
         if (A[j] < A[smallIndex])
            smallIndex = j;
      // 將這一趟找到的最小元素與A[i]交換
      Swap(A[i], A[smallIndex]);
   }
}
#endif