//inss22.c -- 插入排序法 補充說明 第二版
//為了讓大家更容易了解 Insertion sort (插入排序法) 演算法,
//   我再把 inssort.c 用更白話文方式解釋 :-)
//    用註解方式把各環節與各小函數都加上說明! 
// 注意喔, 此例每筆資料包括三項,  但分散在三個 array 內!
/// 
//   如果使用 struct, 就..
// 就可把該三項先用 struct 定義一個新資料結構例如 Student, 
//   這樣相關資料(例如同一個學生的資料)就可被放在一起,
// 全部學生資料變成一個 array, 不會分散成很多 array,
//  要 copy 或 要對調就會很方便 ! 
/// 所以,  
// 這範例比較像我們現在要做的習題: 
//    每位學生的資料有很多項目 ! 


//inssort.c  -- by tsaiwn@csie.nctu.edu.tw === Insertion sort
// 插入排列法 (插隊排序法), 很像排隊時插隊, 但要插到正確位置!
// 想像你到一個已經由高到矮或由矮到高排好的隊伍,
// .. 然後你要排進去, 且要插入到正確位置, 你會怎麼做?
// .. 電腦中 array 可以假裝後面的"還沒來", 
// (1) 一開始只有一個 data, x[0], 當然有排好, 然後每次多看一個,
// (2) 第二位 x[1] 來了, 怎辦? (令 i=1; 稱這為 x[i];)
//     (a)先站到臨時區 tmp = x[i];  // 注意 i 是 1
//     (b) k 指向 x[i] 的前一位, 就是說 k = i-1; // 此時是 0
//     (c) Loop until k 已經指到沒人處(就是k已經小於0): 
//             k 指的那位與 tmp (目前這位) 比,
//             看要不要拉下來一格, 就是 x[k+1] = x[k];
//             若有拉下來, 須再往前 check, 除非前面已沒人
//             阿就是要 k = k-1; 
//     (d) 此時 k+1 是這傢伙的位置, 
//         所以做 x[k+1] = tmp; 
// (3) 第三位 x[2] 來了, 怎辦? 阿就重複 (2)的動作啊 (注意 i =2;)
//  ...
// (n) 第 n 位 x[n-1] 來了, 還是重複(2)的動作啊 (注意 i = n-1;)
//    注意因 array 從 x[0] 開始, 因此這說的第 n 位是 x[n-1];
/// 所以, 從(2)到(n) 這些合起來就是: 
///  for(i=1; i <= n-1; ++i) {  // 我要讓 x[i]到對的位置
///      tmp = x[i];
///      k = i -1;
///      while(k >= 0 ) {  // 看看要不要把 x[k] 拉下一格
///         若 x[k] 已經是不會比 tmp 大那就離開這while Loop
///         不然把 x[k] 拉下一格, 就是把第 k 個 copy 去 k+1位置
///         k = k -1;  // --k;   //再看更前面一個
///      }//while k
///      把 tmp copy 到 x[k+1];  //  k+1 那位置是我該在的位置啦
///  } // for i 
////// 
///  綜上所述, 每次看一個資料, 就是前面都已排列好, 接著要..
// 用排隊時的方法把"剛剛來到(看到)"的那個傢伙排到正確位置!
// ... 這就是所謂的 Insertion sort 啦!
/// 注意, 這範例已經把"每個人的資料" ..
/// .. 擴充為每人有三項喔 ! 放Global 方便存取!
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define N_MAX 88

//以下是這範例處理的資料, 分散在三個 array
//從這個例子可以發現如果有 struct 該多好!
//三個 array 已經夠麻煩!
//萬一要處理的每筆資料有數十項那就很 狠 狠 麻煩!
//就算有些可以用兩度空間陣列(two dimensional array)也還是麻煩!
//這就是雖然可以不用 struct 就能寫出所有程式,
//   但是若可以用 struct 那就太爽了!!
///   把資料 group (或說aggregate)在一起, 就可看作一個變數!
///    對調時或 copy 時都只要一個句子就寫完!
///===

int x[ ] = { 33, 88, 58, 92, 50, 85, 66, 68};  //記得要 ";"
const int nStu = (sizeof x / sizeof x[0]); 
// 上面這招我們已經用過很多次!!
// 就是讓 compiler 自動幫我們算 x[ ] 有幾個元素, 因為:
// sizeof x 是 x[ ]的總 Byte 數, sizeof x[0] 是一個元素的Byte數

float x2[ ] = {180.5, 172, 166.2, 170, 168, 159.5, 173, 165.3};
char x3[ ][9] = { "張三", "李嗣五", "陳火扁", "李等毀", "哈拉",
         "馬扁騙", "李博文", "宋雖委"}; 
/// 上面共三個 array, 彼此是有相關的!
/// x[5], x2[5], x3[5]  是同一筆(同一個人)的相關資料
///   ==> 注意排序過程不可弄成張冠李戴喔!!!

//以下這 function 會把資料從 [0] .. 到 [n-1] 都印出來! 每列一筆!
void printArray(int n) {
  int i;
  for(i = 0; i < n; i++) {
     fprintf(stdout, "%d %5.1f %s\n", x[i], x2[i], x3[i]);
  } // for i
}

// 以下是用來比較兩項資料的 比較函數 (compare function)
// 相等回傳 0, a < b 回傳負數 (通常應該回傳 -1 ), a>b 回傳正數
//  注意若 a, b 是實數, 最好用 if(a<b)return -1; 
//  if(a>b) return 1; if(a==b) return 0;
// 否則若直接回傳 a-b; 可能有時有問題, WHY? (Hint: 0.2當整數是 0)
int compareINT(int a, int b) {  // compare function
    return a - b;  // 這樣就可以了 ; 改 return b-a; 再試看看 
} // for Ascending order
 
int cmpGGG(int a, int b) {  // another compare function
    return b - a;  // 與前面 return a-b; 相反喔! 
} // for Descending order 遞減序
// 
// 以下是 Global 變數, 用作臨時區暫放的
// 因為每筆資料有三項, 沒使用 struct 就是這麼麻煩 !
/// 如果有 struct 可以用, 這三項就可合起來成一個變數喔! 
int tmp; float tmp2; char tmp3[9];   // for temporary area


///以下 copy2tmp(i) 會把所有array 第 i 個資料 copu to temp 區 
/// 注意 x3 和 tmp3 是字串(char array), 要用 strcpy 這程式庫函數
/// 因為 strcpy 在  <string.h> 宣告的, 要記得 #include 喔 ! 
void copy2tmp(int i) {  // i-th data to tmp
   tmp = x[i]; tmp2=x2[i]; strcpy(tmp3, x3[i]);
} // 因為不只一項, 寫成 function 卡好用 :-)


//以下 copyBack(i) 會把 temp 區資料 copy 回所有array 第 i 個
//////  阿這例子包括 x[i], x2[i], 以及 x3[i]
void copyBack(int i) {  // from temp area to  i-th data
   x[i] = tmp; x2[i] = tmp2;  strcpy(x3[i], tmp3);
} // copyBack(


//以下 pullDown(i) 會把第 i 個的所有資料 copy 到第 i+1 個位置
void pullDown(int i) {  // 注意有三項喔 ! move ?[i] to ?[i+1]
   x[i+1] = x[i]; x2[i+1] = x2[i];  strcpy(x3[i+1], x3[i]);
}


// 注意這插入排序法 (插隊排序法)使用一個 compare function
// .. 這樣你只要改變比較函數, 就可改變排序的方向: 遞增或是遞減
// 這版的compare function 是傳入的, 它要負責比較兩個整數參數!
///  Sorting function 會把兩個整數資料傳過去給該 比較 函數
// 再注意: 這 compare function 與 Library qsort( ) 要的比較函數不同!! 
/// 所以這個 InsertionSort 只能比整數(就是 key 是整數)
/// 若要甚麼都可比, 必須把 comp( )的參數改為 pointer
/// 當然從這 sorting function 傳給 comp( )的也須為 pointer, 
/// 且 comp( )自己要轉(cast)為自己知道的型別!
////// (請參考給大家Lab12/Lab13的參考解答)
 
  
void insertionSort(int n, int(*comp)(int,int) ) { //注意比較函數
             // ALL data in global variable
  // Insertion sort method, sort n records in array int x[ ];
  int i, k, flag;  // flag 在這沒用, 在 Bubble sort 才有用!
  //int tmp;   // 因不只一項, 移去外面方便用 function 處理!
  for(i = 1; i < n; i++) {  // 0-th already sorted
     // 首先看做第 i 個剛剛來 (i+1)以後的先假裝沒看到 !
     // ..所以, 先把 [i] copy to temporary 臨時區
     copy2tmp(i);  //tmp = x[i];  // i-th 先站到一邊去
        /// ..
      // 再來利用 k 指向逐一要 check 看是否該拉下來一格?
     k = i-1;  // 從我的前面那位開始看要不要拉他下來一格?
      // 開始用 while Loop 逐一往前檢查 (每次 --k; )
      // .. 當然每個 [k] 都是要跟我 (tmp) 比
      //... 如果你要比別的資料, 記得臨時資料有 tmp, tmp2, tmp3
      //  但type不同! 注意 tmp3 是字串, 要用strcmp()才可比字串!
     while( k >= 0 ) {   // 注意  k 最小到 0 
        // if(x[k] <= tmp) break;  // ascending order
        if( comp( x[k], tmp) <= 0 ) break;  //  改 >=0 會怎樣?
         // 上面這 if 是說 x[k] 小於或等於 tmp;
         // 那就不要再 "拉他下來 " 了! tmp 要排x[k]的下一位啦!
         // 所以就 break; 然後要 copyBack 到 k+1 位置!
        pullDown(k); // x[k+1] = x[k];  // pull it down
        --k;   // 再 check 往前面一位; 注意前面 while(k>=0)
     }//while k
     copyBack(k+1);  //x[k+1] = tmp;  // 站回該站的位置
           // 記得要 copy 到  k+1 處喔, 不是 [k]喔, Why?
  } // for i
}// insertionSort(
 
// 看完這個範例, 你應該可以寫出Lab12的把學生資料排序習題了 
// 只要稍微修改這範例, 就可拿去併入到 hwk1213.c 用 :)
// 你也可以參考這範例去修該 bbsort.c 或 selsort.c 併入hwk1213.c
 
int main() {
  int i, k, nRecord;
  // set Seed for rand() to force true random
  fprintf(stderr, "Demo Insertion Sort ... ");
  nRecord = nStu;   // global
  //
  fprintf(stdout, "\nBefore Sort\n--- ---\n");
  printArray(nRecord);  
   ///
  insertionSort(nRecord, compareINT);  // data in 3 global array
   ///
  fprintf(stdout, "\nAfter Sort\n--- --- ---\n");
  printArray(nRecord); 
  fprintf(stdout, "\n Sorting wiht cmpGGG\n");
  insertionSort(nRecord, cmpGGG);  // data in 3 global array
  fprintf(stdout, "\nAfter Sort with cmpGGG\n--- --- ---\n");
  printArray(nRecord); 
  fprintf(stderr, "\nHit ENTER key...");
  getchar( );  return 0;
} // main(  
/******
D:\test> path C:\Dev-Cpp\bin;%path% 
D:\test> gcc inss22.c 
D:\test> a.exe 
Demo Insertion Sort ...
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 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 李等毀

 Sorting wiht cmpGGG

After Sort with cmpGGG
--- --- ---
92 170.0 李等毀
88 172.0 李嗣五
85 159.5 馬扁騙
68 165.3 宋雖委
66 173.0 李博文
58 166.2 陳火扁
50 168.0 哈拉
33 180.5 張三

Hit ENTER key...

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