// selAlg.c
/// 為了讓大家更了解 Selection sort (選擇排序法)
/// 我用另外兩個 selection sort 範例補充說明!
/// 此處的 Student_t 是自己定義的 struct

/// 想像你要把書架上的書由左到右排列好:
 /// (1)假設每本書厚度一樣, 但高矮不同
 /// (2)假設每本書都很重 :) 
 /// 想一想, 要怎樣把它們照左邊最高右邊最低排好(或相反)?

// 第 0 次:  選出最高的, 把它跟第 0 本(最左)對調
// 第 1 次: 把第 0 本看作不存在 (就不要管它啦)
//           從第 1 本到最後一本(第 n-1本),
//           重複做與第 0 次相同的事, 最高的與第 1 本(最左)對調
// 第 2 次: 把第 0 本, 和第 1 本都看作不存在 (就不要管它們啦)
//           從第 2 本到最後一本(第 n-1本),
//           重複做與第 0 次相同的事, 最高的與第 2 本(最左)對調
// ...
// 第 n-2 次: (這是最後一次)  (這時只剩下兩本)
//           找出 從第 n-2 本到最後一本(第 n-1本)中最高的,
//             把最高的與 第 n-2 本對調!
//   .. 注意, 每次都有可能是 "自己跟自己對調"!
//   .. 但那樣仍是不會有問題 ! WHY ?

typedef struct {
    long sid;
    // 其他資料

} Student_t;

// /// /// /// /// /// /// /// /// /// /// ///
/// 以下這版本寫成會把 x[ ] 照學號 (sid) 排遞增序 Ascending 
/// 可以改寫成將比較函數傳入這 sort 函數, 不要直接比較
void swapSelection(Student_t*x, int n) {  // swap version NOT stable
  // selection sort method, sort n records in array int x[ ];
  // Ascending order 遞增++, this version is NOT a stable one :-)
  int i, k, min;
  Student_t tmp;   // 類似兩杯水要對調, 須拿個空杯子來用 
  for(i = 0; i <= n-2; i++) {  // 0.. n-2
     min = i; // 假設我最小, 走遍 i-th 之後的全部, 找出最小者
     for(k=i+1; k <= n-1; ++k) { // 從第 i+1 個開始找
          // k ==>  i+1, i+2, ..., n-1 (最後一個)
        if(x[k].sid < x[min].sid) min = k; // 有人比我小, 記住它(k)
     }// for k
     /// /// step-2 --- swap i-th with the min one
     tmp = x[min];  x[min]=x[i];  x[i] = tmp;  //對調的基本動作
  } // for i
  return; // done!  注意這版本不是  Stable 
} //swapSelection(


////// 寫個 compare function 給以下 sort 用
/// 注意傳入的 i, k 是指第幾個, 不是資料本身 
int compHaha(Student_t*x, int i, int k) {  //第 i 個與第 k 個比
    return x[i].sid - x[k].sid;  // 整數用相減就可以啦 
} //compHaha(
///
/// /// //////// === Stable Selection sort === //////// /// ///
 /// 這版本因為選到要的之後是用"塞入" (insert)方式,
 ///  須把塞入位置之右邊全部(到抽出的那本為止)都各往右移動一格,
 /// 所以, 一定會比較慢, 尤其當"移動一格"的成本較高時更慢!
 ///  不過, 其實也差不了多少啦  :-)
 /// 所謂"移動一格"的成本較高就是, 若"一筆"含有很多項目!
 /// 例如, 一位學生的資料有學號, 姓名, 身高, 體重, ... 各科成績
 /// 因為用"塞入方式", 所以這版是 Stable 的喔!
 /////// 還有, 這版本 已經寫成使用 傳入的 compare function 
 ////// 使用時要將 "比較函數" 傳入這 sort 函數, 我們不直接比較!
 /////// 這樣就較容易改變排序的 key, 只要換掉比較函數就可!!
void selSort(Student_t*x, int n,
      int(*comp)(Student_t*, int, int)
                     ) {  // n 個學生資料要 sort 
  // selection sort method, sort n records in array int x[ ];
  // Ascending order 遞增++, this version is a STABLE one :-)
  // But 因選到後用"塞入"(INSERT), 要移動右邊全部, 比較慢!
  int i, k, min;
  Student_t tmp;   // 空杯子 (臨時變數)
  for(i = 0; i <= n-2; i++) {  // 0.. n-2
     min = i; // 假設我最小, 走遍 i-th 之後找出最小者
     for(k=i+1; k <= n-1; ++k) { // 從第 i+1 個開始找到最後
        if( comp(x, k, min) < 0 ) min = k; // 有人比我小, 記住它
     } // for k
     // step-2 insert that one into position i
     // move down all elemensts between x[i] and x[min-1]
     // 就是要把 x[min-1] copy 到 x[min], ...
     tmp = x[min];  // save the min one for later use
        // 等於把選到的那本(min)抓到手上(tmp)
     while(min > i) {   // 別寫錯, min 每次減一到 i 右邊為止
        x[min] = x[min-1];   // 例如 8--> 9,  7--> 8,  6--> 7, ...
        --min;
     }// while; 注意停的時候 min == i
     // 位置挪出來了(第 i 個), 所以把手上(tmp)的放入 x[i]
     x[i] = tmp;  // 它該在這位置! 因 x[i]已經在剛剛被copy到x[i+1]
  } // for i; i==0, 1, 2, ... n-2
  return; // done
} //selSort(
///
// gcc -c selAlg.c
// nm selAlg.o
/**************
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> gcc -c selAlg.c
D:\test> nm selAlg.o
00000000 b .bss
00000000 d .data
00000000 t .text
000000ba T _compHaha
000000e3 T _selSort
00000000 T _swapSelection
D:\test>
************************/