// sel22.c  --- another selection example void select3388( ) 
/// @CopyLeft by tsaiwn@cs.nctu.edu.tw
//////
/// 為了讓大家更了解 Selection sort (選擇排序法)
/// 除了已經給的另外兩個 selection sort 範例補充說明! (selAlg.htm)
/// 再給一個把 inssort.c 拿來改寫為 Selection sort 的版本
///// 再參考這個版本, 應該更覺得這次 sorting 習題真的不難了吧!
////// 
/// 且注意這版本不是  Stable (穩定的)
///// 因為, 此例子仍是不使用 struct, 可是"每個人"有多項資料,
///// 所以, 為了方便, 把 "對調 "(swap) 的工作寫為函數!
/// 因為以後 C++ 的程式庫就有把兩變數對調之 template function 的 swap
/// 這範例中我們的版本並非把參數對調, 而是傳兩整數告知要調換的位置
///// 然後, 函數中將三個 array 依照指示把對應的位置都對調;
/// 這與 C++ 程式庫的 swap(x, y) 會直接把參數 x 與 y 對調不同!
/// 因此, 我們取個不同名字叫做  mySwap(int, int) 
/// P.S. 要直接把參數對調在  C++ 是使用 Call by reference; 在 C 做不到!
//////還有, 跟 inssort.c 內的 copy2tmp 等也不同!
//////因為, 我們需要的是"對調", 但 insertion sort 用的並不是對調!!
//////請把這範例跟之前的 inssort.c 對照著看
/// Selection sort (選擇排序法):
////// 
/// 想像你要把書架上的書由左到右排列好:
 /// (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 本對調!
///這樣總共做了 n-1 次 (pass, 回合, 趟)
//   .. 注意, 每次都有可能是 "自己跟自己對調"!
//   .. 但那樣仍是不會有問題 ! WHY ?
///
// 這 例子不使用 struct, 資料與 inssort.c 一樣散在三個 array
// 所以, 我們偷懶不使用參數傳遞, 乾脆放  Global 共用:-)
///
// /// /// /// /// /// /// /// /// /// /// /// 
#include <stdlib.h>
#include <stdio.h>
/// 以下這版本寫成會使用傳入的比較函數, 類似程式庫 qsort 的做法
/// 就是說兩項如何比我並不知道, 你必須寫一個 compare function 傳給我
/// 然後, 我要比較大小就 call 你給我的 function,
/// 不過跟程式庫 qsort( ) 的compare function 不同!
/// 我這要得 compare function 必須接受兩個整數, 都是代表第幾個,
/// 然後 compare function 也是要傳回 -1, 0, 1 表示兩項的大小
///// 如果左邊大於右邊就傳回 1, 左邊小於右邊就傳回 1, 相等回傳 0,
////// 這樣, 我會幫你把資料照你的 key 排成由小到大 (Ascending,遞增)
////// 若你要的是遞減, 那就在 compare function 做相反就好!
////////
/// 注意因為 data 在三個 array, 所以偷懶使用 Global variable
//////
int x[ ] = { 33, 88, 58, 92, 50, 85, 66, 68};
const int nStu = (sizeof x / sizeof x[0]);
float x2[ ] = {180.5, 172, 166.2, 170, 168, 159.5, 173, 165.3};
char x3[ ][9] = { "張三", "李嗣五", "陳火扁", "李等毀", "哈拉",
         "馬扁騙", "李博文", "宋雖委"};
/// 
/// 以下會把各 data 的 i-th 與 k-th 項目對調
void mySwap(int i, int k) {  // swap i-th  with k-th
     int tmp; float tmp2; char tmp3[9];  // 注意各 type
   tmp=x[i],  x[i]=x[k],   x[k]=tmp;
   tmp2=x2[i]; x2[i]=x2[k]; x2[k]=tmp2;  // 別寫錯變數喔
   strcpy(tmp3, x3[i]); strcpy(x3[i], x3[k]); strcpy(x3[k], tmp3);
}// mySwap 
// 仔細看看以下 選擇排序法, 只是把本來只排序一個 array 的略作修改!
void select3388(int n, int(*comp)(int,int)) {  
   // swap version NOT stable
  // selection sort method, sort n records of data in 3 array 
  // Ascending order 遞增++, this version is NOT a stable one :-)
  int i, k, min;
  for(i = 0; i <= n-2; i++) {  // 0, 1, 2, .. 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)
         if( comp(k, min) < 0) min = k;  // 類似騎驢看馬 :-)
     }// for k
     /// /// step-2 --- swap i-th with the min one
     /// tmp = x[min];  x[min]=x[i];  x[i] = tmp;  //對調的基本動作
     mySwap(i, min);   // 第 i 個與第 min 個資料對調
  } // for i
  return; // done!  注意這版本不是  Stable sort
} //select3388(  
///
void printArray(int n) {  // 有 n 筆資料要印出 
  int i;
  for(i = 0; i < n; i++) {
     fprintf(stdout, "%d %5.1f %s\n", x[i], x2[i], x3[i]);
  } // for i
}// printArray(  
////// 寫個 compare function 給 sort 用
/// 注意傳入的 i, k 是指第幾個, 不是資料本身 
int myComp(int i, int k)  {  // 注意不是直接比資料 !
   if(x[i] > x[k]) return 1;   // Ascending order
   if(x[i] < x[k]) return -1;
   return 0;
} // myComp( 
/// 再寫一個compare function, 顛倒順序 (由大到小)
int yourComp(int i, int k)  {  // 注意不是直接比資料 !
   if(x[i] > x[k]) return -1;   // Descending order
   if(x[i] < x[k]) return 1;
   return 0;
} // yourComp( 
///再一個compare function, 比 x2[ ] 內容 (身高? )
int comp22(int i, int k)  {  // 注意不是直接比資料 !
   if(x2[i] > x2[k]) return -1;   // Descending order
   if(x2[i] < x2[k]) return 1;    // 高到矮 :-)
   return 0;
} // comp22( 
/// /// ///  
int main( ) {
  int i, k, nRecord;
  // set Seed for rand() to force true random
  fprintf(stderr, "Demo Selection Sort select3388( )... ");
  nRecord = nStu;   //  nStu 是 Global 變數
  //
  fprintf(stdout, "\nBefore Sort\n--- ---\n");
  printArray(nRecord);  
   ///
  select3388(nRecord, myComp); // data in 3 global array
   ///
  fprintf(stdout, "\nAfter select3388 Sort\n--- --- ---\n");
  printArray(nRecord); 
  printf("Again, sort with another compare function...\n");
   /// 傳入不同的 compare function, 就可排出不同的結果!!
  select3388(nRecord, yourComp);
  printArray(nRecord); 
  ///
  printf("Again, again, 這次用 comp22 比身高...\n");
  select3388(nRecord, comp22);  // 注意  comp22 是比身高
  printArray(nRecord); 
  fprintf(stderr, "\nHit ENTER key...");
  getchar( );  return 0;
}// main(  
/**************  
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> gcc sel22.c
D:\test> a.exe
Demo Selection Sort select3388( )...
Before Sort
--- ---
33 180.5 張三
88 172.0 李嗣五
58 166.2 陳火扁
92 170.0 李等毀
50 168.0 哈拉
85 159.5 馬扁騙
66 173.0 李博文
68 165.3 宋雖委

After select3388 Sort
--- --- ---
33 180.5 張三
50 168.0 哈拉
58 166.2 陳火扁
66 173.0 李博文
68 165.3 宋雖委
85 159.5 馬扁騙
88 172.0 李嗣五
92 170.0 李等毀
Again, sort with another compare function...
92 170.0 李等毀
88 172.0 李嗣五
85 159.5 馬扁騙
68 165.3 宋雖委
66 173.0 李博文
58 166.2 陳火扁
50 168.0 哈拉
33 180.5 張三
Again, again, 這次用 comp22 比身高...
33 180.5 張三
66 173.0 李博文
88 172.0 李嗣五
92 170.0 李等毀
50 168.0 哈拉
58 166.2 陳火扁
68 165.3 宋雖委
85 159.5 馬扁騙

Hit ENTER key...

D:\test> 
************************/