//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
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] = { "張三", "李嗣五", "陳火扁", "李等毀", "哈拉",
         "馬扁騙", "李博文", "宋雖委"};
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
}
int comp(int a, int b) {  // compare function
    return a - b;  // 這樣就可以了 ; 改 return b-a; 再試看看 
} // for Ascending order
int tmp; float tmp2; char tmp3[9];   // for temporary area
///
void copy2tmp(int i) {  // i-th data to tmp
   tmp = x[i]; tmp2=x2[i]; strcpy(tmp3, x3[i]);
} // 因為不只一項, 寫成 function 卡好用 :-)
void copyBack(int i) {  // from temp area to  i-th data
   x[i] = tmp; x2[i] = tmp2;  strcpy(x3[i], tmp3);
} // copyBack(
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]);
}
void insertionSort(int n) { // ALL data in global variable
  // Insertion sort method, sort n records in array int x[ ];
  int i, k, flag;
  //int tmp;
  for(i = 1; i < n; i++) {  // 0-th already sorted
    copy2tmp(i);  //tmp = x[i];  // 先站到一邊去
    k = i-1;  // 從我的前面那位開始看要不要拉他下來一格?
    while( k >= 0 ) {   // 注意  k 最小到 0 
       // if(x[k] <= tmp) break;  // ascending order
       if( comp( x[k], tmp) <= 0 ) break;  //  改 >=0 會怎樣?
       pullDown(k); // x[k+1] = x[k];  // pull it down
       --k;   // 再 check 往前面一位 
    }//while
    copyBack(k+1);  //x[k+1] = tmp;  // 站回該站的位置
  } // for
}// insertionSort(
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);  // data in 3 global array
   ///
  fprintf(stdout, "\nAfter Sort\n--- --- ---\n");
  printArray(nRecord); 
  fprintf(stderr, "\nHit ENTER key...");
  getchar( );  return 0;
} // main(
/******
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 李等毀

Hit ENTER key...
*****************************/