//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 #include #include #include #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(ab) 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 在 宣告的, 要記得 #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> ************************/