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


//inssort.c  -- by tsaiwn@csie.nctu.edu.tw === Insertion sort
// 插入排列法 (插隊排序法), 很像排隊時插隊, 但要插到正確位置!
// 想像你到一個已經由高到矮或由矮到高排好的隊伍,
// .. 然後你要排進去, 且要插入到正確位置, 你會怎麼做?
// .. 電腦中 array 可以假裝後面的"還沒來",
// .. 一開始只有一個 data 當然有排好, 然後每次多看一個,
// ... 用排隊時的方法把"剛剛來到(看到)"的那個傢伙排到正確位置!
// ... 這就是所謂的 Insertion sort 啦!
/// 注意, 這範例已經把"每個人的資料" ..
/// .. 擴充為每人有三項喔 ! 放Global 方便存取!
#include <stdlib.h>
#include <stdio.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 comp(int a, int b) {  // compare function
    return a - b;  // 這樣就可以了 ; 改 return b-a; 再試看看 
} // for Ascending 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 也可當作函數的參數傳入! 以後講!!
 
void insertionSort(int n) { // 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