//hwk13tq2.c --- @CopyLeft by tsaiwn@cs.nctu.edu.tw // 測試 qsort2( ) 1000 次 --- 透過 LAB13 (Lab11, Lab12, Lab13) /// 這範例也是 Lab13 的參考答案, 用struct+我們自己寫的 quick sort ////// 若你 Lab12 有做出來, 請先不要看這範例, 先自己試著做出 Lab13 /// 其實, 這範例只是把之前給大家的 hwk12qsort.c 略為修改: /// (1)改用自己寫的 qsort2( ), 但你可用 -D 指定換為其它兩個之一 /// (2)Default 測試 1000次, 你可用 -DRUN=38 改為 測試 38 次 // gcc hwk13tq2.c qsort2.c qqsort.c (這樣沒用到的也Link一起) // gcc hwk13tq2.c -DQSORT (這樣變為用Library的 qsort) // gcc hwk13tq2.c -DQQSORT qqsort.c -DRUN=100 (這用 qqsort 測100次) #define NNRUN 1000 //#include "qsort2.h" // 已經自己宣告在下面免得者不到該檔案 #define QK_SORT qsort2 #define SORT_USED "qsort2" // 改上面兩列就可換成使用別的 sorting function /// SORT_USED 是用來印出訊息, 請務必與 QK_SORT 一致, 不然言行不一致? // 以下讓 User 可以不必改程式碼, 只要改 compiling option -D // 用 conditional compiling 特性的 -DQQSORT 或 -DQSORT 就可改變 // 不過要記得 qsort2( ) 在 qsort2.c, 還有 qqsort( ) 在 qqsort.c /// 所以要記得所需檔案或乾脆 gcc hwk13tq2.c qsort2.c qqsort.c -D選項 #ifdef QQSORT #undef QK_SORT #undef SORT_USED #define QK_SORT qqsort #define SORT_USED "qqsort" //#include "qqsort.h" #endif #ifdef QSORT /* C_Built_in qsort( ) */ #undef QK_SORT #undef SORT_USED #define QK_SORT qsort #define SORT_USED "qsort" #include #endif #ifdef QSORT2 /* use qsort2( ); nothing to do */ //#include "qsort2.h" #endif #ifdef RUN // 換成 User 指定的次數 // 例如 gcc -DRUN=38 ... #undef NNRUN #define NNRUN RUN #endif //#define QK_SORT qqsort //#define QK_SORT qsort // gcc hwk13tq2.c qsort2.c // 或 gcc hwk13tq2.c qqsort.c // 或 gcc hwk13tq2.c qsort2.c qqsort.c (這樣沒用到的也Link一起) /// 修改上面的 #define QK_SORT qsort 就可換為 Library qsort( ) /// 你可以把 qsort2( ) 換成之前給的 qqsort( ) 再測試看看 /// 或是換回 C Library 的 qsort( ) 測試看看 /// 應該差不多一樣快 :-) 測試一千次再比看看比較公平 /// 事實上是我寫的 qsort2( )比程式庫的 qsort( ) 快一點點 :-) /// 用 C Library 的 qsort( ) : 約 69 秒, 比qsort2( )的62秒慢 ///// 不過 qqsort( ) 卻慢了一點點 :-( //#include "qsort2.h" //#include "qqsort.h" // void qsort2(void*x, int n, int size, int (*cmp)(const void*, const void*) ); void qqsort(void*x, int n, int size, int (*cmp)(const void*, const void*)); /// 本來上述宣告是放 qsort2.h 和 qqsort.h 給你 #include // 直接宣告以免找不到上述兩個 Header file "qsort2.h", "qqsort.h" ////// ////////////////// 2010/12/03 Friday //hwk13tq2.c ----- sample program to SORT studat.txt //========== Originally by tsaiwn@csie.nctu.edu.tw /// const char *hahaha = " \n" " 五都選舉已結束, 幾家歡樂幾家幹; \n" " 太陽依舊很燦爛, 輸贏已定賣靠餐\。 \n" " 選舉結果放兩邊, 作業練習擺\中間; \n" " 若真想要不被當, 習題必須多多練! \n" // 那個ㄅㄞˇ 有問題 " .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?!\n"; /// 上面的"擺\" 反斜線不可以去掉, 不然翻譯有錯!! /// /// 因為 擺\爛 的 "擺\" 之內碼是0xc2 0x5c; 0x5c 是反斜線 !! ////// 阿字串中的 \ 是逃脫字符! 例如 \n 是 NewLine, \t 是跳格 ////// 所以 "\\" 就變成一個反斜線! What if 內碼第一Byte是 \ ? ////// 如果註解 // 後面的最後一個字是 擺 阿那會怎樣呢??? /// /// 注意, 這範例只做照學號排序(sorting), 照題目規定應該.. /// 請看習題說明, 關於 全部同學的平均 和 標準差.. /// 在資料看完一遍後就可算出來! 不必先算平均喔! /// .. 算這些統計資料的做法以前範例已經給過, 再不懂舉手問 :-) // 站在巨人的肩膀上: // 這版本是偷用 C 程式庫中的 qsort( ) 做排序 (現改用 qsort2) // 注意使用 qsort2( ) 須先照規定寫好 call back function // .. 阿就是compare function 參數要照規定接受兩個 const void* // *** 想要不同順序, 只要寫不同的 compare function 傳給qsort2 // *** 注意， qsort2 只知道資料是連續一堆 bytes, // *** 每當它想比較, 就會把兩項資料在記憶體的起點傳給比較函數 // *** 所以比較函數的參數是 (const void*, const void*) ///*** 你的比較函數必須自己轉換成你知道的型別(type) ///*** 因為你 call qsort2( ), 然後 qsort2( ) 回頭 call 你寫的 ///*** .. call 你寫的 比較函數, 所以稱為 call back function! #include #include #include #include char* fileName = "studat.txt"; // Data File long test( ); // 會傳回有幾個 records /// /// 雖然定義 struct 有很多寫法, 建議用這種寫法: typedef struct { long sid; int s1, s2, s3, s4; // struct 內各項目順序不重要 double total; // 學期總成績= (h*0.2 + m*0.3 + q*0.1+f*0.4); /// 這裡的 s1, s2, s3, s4 就是 h, m, q, f long rank, recno; // rank, original record number char name[9]; // student's name } Student_t; // 這種命名方式是不錯的習慣 ( _t) /// void sort(Student_t*, long left, long right); // sort( ) is your sorting program according to the score // left 是開始那項的 index, 最後一筆是 right void sort2Print(Student_t*, long n); // n records // sort2Print() is your another sorting program (照學號) // 注意我故意把參數用不同的寫法 ! 不是第幾個到第幾個 void print(Student_t*, long,int); // 用來印出資料, 但只印出一部份! ////// 第三個參數是個 FLAG, 表示要不要印名次 ? void readALL(Student_t *y, long, char*file,double*s,double*ss); // read ALL data from file into y[ ]; s=sum, ss=sum of square /// void perm(Student_t *stus, long n) ; // 用來把資料弄亂 (洗牌) double testSort(Student_t *stus, long n) ; // 改用這測試 sort // 注意 testSort( ) 會傳回來用了多少 秒 int main( ) { Student_t * stus; // 等一下用 malloc 要記憶體, 當作 stus[ ] long long tStart, tStop; long i, k, n; double tRun; double sum, sumSquare, average, variance, std; n = test( ); // 這列以上不准改! test( )會傳回 record 數目 fprintf(stderr, "Sorting using function %s, " " test %d time(s).\n\n", SORT_USED, NNRUN); // 打開檔案讀資料到記憶體, 也可寫成 function 在此 call 它 ! // 一邊讀, 一邊算出每個人的學期總成績; 或讀完再算也可以! // ..注意, 還要算出全部同學的平均 和 標準差 stus = (Student_t*) malloc(sizeof(Student_t)*n); // n 筆 // Note that malloc( )的單位是 Bytes // in C++: stus = new Student_t[n]; readALL( stus, n, fileName,&sum, &sumSquare); //into stus[ ] // 記得要用 "&" 把 sum 和 sumSquare 的address傳過去 average = sum / n; // 以下變異數公式以前給過, 忘了就上網查 variance = (sumSquare - sum*sum/n) / n; // sumSquare是平方和 std = sqrt(variance); // 高中就學過"變異數開根號就是標準差" printf(" N= %ld, Average= %.2f, STD標準差= %.3f\n", n, average, std); printf("Before sort...\n"); print(stus, n, 0); // 叫用 print( ) 印出部份資料, 不印名次 // todo.. print average, standard deviation tRun = 0.0; // tRun 是以秒為單位 for(i=1; i<= NNRUN; i++) { perm(stus, n); // 弄亂, 每次弄亂再 call sort 比較公平 tRun += testSort(stus, n); // 累計每次 sorting 時間 } printf("\nSorting %d times in %.5f seconds\n", NNRUN, tRun); /// fill in the rank (填入名次) for(i=0; i< n; i++) stus[i].rank = i+1; // 第 0 個是第一名 printf("After sort...\n"); print(stus, n, 1); // 叫用 print( ) to print partial data+名次 // Extra credit: 要有名次, 同分者比期末考, 再同比期中考, .. /// /// part 2 sort2Print(stus, n); // 在裡面做照學號由小到大sort, 要測時間 printf("=== 用gen333.c生的資料是常態分佈, 不是 Uniform 分布!\n"); printf(" N= %ld, Average= %.2f, STD 標準差= %.3f\n", n, average, std); printf("==> 站在巨人肩膀上: 本程式這次是叫用函數 %s,\n\t" "Sort %ld 筆資料依成績遞減 Descending 用了平均 %.5f 秒.\n", SORT_USED, n, tRun/NNRUN); printf("Hint: 用 rand( )%%32767/32767.0 生出 12 個數加總, " "然後減去6.0;\n\t這樣就是 N(0, 1)的常態分配亂數;\n" "\t把這亂數乘以你要的標準差, 再加上你希望的平均數;\n" "\t.. 這樣, 就會是你希望的常態分佈成績!\n"); printf("\nSorting %d times in %.5f seconds : function %s used." "\n", NNRUN, tRun, SORT_USED); fprintf(stderr, "%s Hit ENTER key...", hahaha); getchar( ); return 0; } // main( /// /// /// ================ ============== ============== /// print one student, with Final grade? with Rank? void printStudent(Student_t yy, int prtFinal, int prtRank); /// void print(Student_t *x, long nStu, int rankFLAG) { // 我用傳參數 // 當程式是由多人合作時, 最好儘量少用 Global 變數 ! int i; for(i=0; i < 6; ++i) printStudent(x[i], 1, rankFLAG); // with total score printf("...\n"); printf("Stu ID name hwk mid quiz fin" " 學期成績 名次\n"); for(i=nStu-5; i< nStu; ++i) printStudent(x[i], 1, rankFLAG); } /// do NOT modify the following code long test( ) { // 這函數不准改 ! 它會回傳檔案內有多少紀錄 long id; char name[9]; int s1, s2, s3, s4, kk; static char buf[99]; FILE* fp; fp = fopen(fileName, "rt"); // read, text if(fp==0) { // Fail to open it fprintf(stderr, "File %s NOT found!\n", fileName); getchar( ); exit(38); // force to exit with an error } fgets(buf, sizeof(buf), fp); // stdin if(feof(fp) ) { fprintf(stderr, "EOF encounted.\n"); return; } //fprintf(stderr, "Line-1: %s\n", buf); fgets(buf, sizeof(buf), fp); // stdin //fprintf(stderr, "Line-2: %s\n", buf); s1=s2=s3=s4=0; kk = sscanf(buf,"%ld %s %d %d %d %d", &id, name, &s1, &s2, &s3,&s4); //printf("kk=%d\n", kk); if( kk != 6) fprintf(stderr, " something Wrong with data!\n"); //printf("id=%ld name = %s\n", id, name); //printf("score= %d %d %d %d\n", s1, s2, s3, s4); fprintf(stderr, " counting..."); fflush(stderr); kk = 2; // already read 2 records while(! feof(fp) ) { // 只要檔案還沒結束 buf[0] = 0; fgets(buf, sizeof(buf), fp); if( feof(fp) ) { // EOF 也可能有讀到不完整的 Line if(buf[0] == 0) break; // 沒有讀到啦 } ++kk; // got one record } fprintf(stderr, " .. done.\nTotal %d records in file %s\n", kk, fileName); // 印到 stderr (螢幕) fflush(stderr); fclose(fp); // close the file return kk; // total kk records in the file } // test( /////////////////// /// 以下myComp is a 比較函數 that will compare 總成績 total, /// 要讓 qsort 做 Descending 排序, 若同分, 則照原 record no遞增 /// ..這樣就等同於 stable(穩定)的 sort; (注意qsort不是 stable !) int myComp(const void*pa, const void*pb) { // for sort( ) 總成績 Student_t * sa = (Student_t*) pa; // cast (轉型) Student_t * sb = (Student_t*) pb; // 其實 cast 電腦沒做任何事 if(sa->total < sb->total) return 1; if(sa->total > sb->total) return -1; /// toal 總成績相同, 比期末考 s4, 仍是遞減序 Descending order if(sa->s4 < sb->s4) return 1; if(sa->s4 > sb->s4) return -1; // 又同分ㄟ, 若要繼續比期中考是在 s2 , 請自己練習 (太簡單 :-) /// 成績同, 以下是比原來讀入的序號, 但用遞增序! if(sa->recno < sb->recno) return -1; // 這樣是遞增 if(sa->recno > sb->recno) return 1; // return sa-sb; return 0; } //myComp( void sort(Student_t x[ ], long left, long right) { // 我用傳參數! // call Library qsort( ), 或 qqsort( ), 或 qsort2( ) QK_SORT((void*)x, right-left + 1, sizeof(Student_t), myComp); // 注意程式庫qsort( ) 要這 4 項資料作參數(另兩個我寫的也比照): // 1.資料起點(address), 2.有幾項, 3.每項多少Bytes, 4.比較函數 // 再注意: "比較函數" 必須接受 兩個指標 (const void*) } // sort( /// /// 再來是 a 比較函數that compares ID, 要讓 qsort 做 Ascending 排 int compID(const void*pa, const void*pb) { // for sort2Print( Student_t * a = (Student_t*) pa; // cast 轉型 Student_t * b = (Student_t*) pb; if(a->sid < b->sid) return -1; //左小右大回傳 -1 : Ascending if(a->sid > b->sid) return 1; return 0; // ID 相同 ? 不管它 ! } //compID( void sort2Print(Student_t *x, long n) { // 要照學號由小到大 ! /// 參數.. // 注意我故意用不同於前面 sort( ) 的寫法喔 ! 此處 n是說有 n 筆 // Ascending order, 記得要量時間, 除了clock( )還有更準的自己查 long long tStart, tStop; // long long 是 64 bits double tRun; printf("...Now Sorting according to student ID..."); tStart = clock( ); QK_SORT((void*)x, n, sizeof(Student_t), compID); // 注意寫法 ! tStop = clock( ); tRun = 1.0*(tStop - tStart)/CLOCKS_PER_SEC; // 注意上面的 1.0* 不可拿掉! Why? printf("\n...Sorting done in %.5f seconds.\n", tRun); /// printf("\n === Now already sorted in Student_ID" " at ascending order.\n"); print(x, n, 1); // call print( ) to print some data+rank } //sort2Print( /// /// 以下的宣告其實是多餘的 ! 因為馬上就要寫了 :-) int readStudent(Student_t * gg, FILE* fp); // read One學生資料 // /// /// read One student data int readStudent(Student_t * stu, FILE* fp) { // default stdin // 這裡的 stu 是一個指標, 指向一個學生 // 注意 default 參數要 C++ 才有, C 不可使用 default 參數 static char buf[999]; int nRead; // 讀到幾項資料? fgets(buf, sizeof(buf), fp); nRead = sscanf(buf, "%ld %s %d %d %d %d", &(stu->sid), stu->name, &(stu->s1), &(stu->s2), &(stu->s3), &(stu->s4) ); /// 題目規定這樣: // 學期總成績= (h*0.2 + m*0.3 + q*0.1+f*0.4); /// 這裡的 s1, s2, s3, s4 就是 h, m, q, f stu[0].total = 0.2*stu->s1 + 0.3*stu[0].s2 + 0.1*stu->s3 + 0.4*stu->s4; stu->total = ((int)(100* stu->total +0.50000001))/100.0; stu[0].rank = 1; // 大家都是第一名 :-); stu-> 改用 stu[0]. 可 stu[0].recno = 0; // 這樣寫 OK, (I do not know recno :-) // 注意, stu[0] 就是 *stu ; 以前說過任何時候 *p 就是 p[0] // 阿所以 stu->gg 就是 stu[0].gg 也就是 (*stu).gg return nRead; // 這是 sscanf 回報給我們的 }// readStudent( /// void readALL(Student_t x[ ], long n, char*file, double sum[ ], double *sumsum) { long i; double tmp; FILE* fp = fopen(file, "rt"); // 偷懶, 不防呆 sum[0] = sumsum[0] = 0.0; // sum[0] 就是 *sum for(i=0; i < n; ++i) { readStudent( &x[i], fp); // 注意 &x[i] tmp = x[i].total; // 該學生的總成績 sum[0] += tmp; // 注意 sum[0] 就是 *sum 啦 sumsum[0] += tmp*tmp; // 平方和 x[i].recno = i; // 注意寫法喔! record no., 0..n-1 // 多把 recno 也記下, 目的是讓 sort 看起來是 Stable // 這是因為 qsort( ) 不是 stable sort // 所以, 我們從 compare function 下手! (看後面該函數) }// for i fclose(fp); // 負責任, 我打開的阿就我自己來關掉它 :) }// readALL( /// void printStudent(Student_t stu, int finalFlag, int rankFlag) { // 注意 default 參數要 C++ 才有, 所以這程式要當作 C++ // finalFlag !=0 ==> 印學期成績; rankFlag 要不要印名次 printf("%8d ", stu.sid); printf("%8s ", stu.name); printf("%3d %3d %3d %3d ", stu.s1, stu.s2, stu.s3, stu.s4); if(finalFlag) { // 這樣寫是若不印 total, 那一定不會印名次! Why? printf("%6.2f ", stu.total); // 學期成績 if(rankFlag) { // 印名次, 須有印學期成績 printf("%5d", stu.rank); // note that stu is a struct }// if rankFlag } // finalFlag printf("\n"); // done }// printStudent( ////// double testSort(Student_t *stus, long n) { long long tStart, tStop; long i, k; double tRun; double sum, sumSquare, average, variance, std; tStart = clock( ); sort(stus, 0, n-1); // call your sort 程式, 照總成績由高到低 // this means to sort stus[0..n-1]; 從 stus[0]..stus[n-1] tStop = clock( ); tRun = 1.0*(tStop - tStart)/CLOCKS_PER_SEC; // in //printf("...Sorting done in %.5f seconds.\n", tRun); fprintf(stderr,"."); return tRun; } // testSort( static long myRand( ) { long ans = rand( ); ans = ans << 15; return ans | rand( ); // 用 31 bits }// void perm(Student_t *x, long n) { long i, k; Student_t tmp; for(i=0; i < n; i++) { // 洗牌 :-) k = myRand( ) % n; tmp = x[i]; x[i]=x[k]; x[k]=tmp; }//for }// perm( /// /// === === === End of the program === === === /// /*********** D:\test> path C:\Dev-Cpp\bin;%path% D:\test> gcc gen333.c -o gen333 D:\test> gen333 File studat.txt generated successfully. Total 81439 student records. Hit ENTER key... D:\test> gcc hwk13tq2.c qsort2.c D:\test> a.exe counting... .. done. Total 81439 records in file studat.txt Sorting using function qsort2, test 1000 time(s). N= 81439, Average= 74.99, STD標準差= 3.859 Before sort... 9933394 陳AAk 79 78 78 66 73.40 9930724 吳HCc 77 80 87 71 76.50 9917439 王IQd 78 80 82 85 81.80 9940985 蔡HCu 71 79 56 78 74.70 9920778 簡EJz 78 81 81 57 70.80 9929263 陳SXl 76 68 67 76 72.70 ... Stu ID name hwk mid quiz fin 學期成績 名次 9998313 李KQz 82 69 62 77 74.10 9998403 孫UJd 85 81 71 74 78.00 9998406 林CHo 74 77 69 83 78.00 9998425 章FHl 78 62 66 72 69.60 9998433 林CKd 78 68 87 84 78.30 ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................................................... ........................................ Sorting 1000 times in 61.78600 seconds After sort... 9945677 蔡WAh 88 91 92 93 91.30 1 9932012 章UFj 85 83 87 99 90.20 2 9953946 趙PTd 77 88 87 97 89.30 3 9927444 林DTm 84 92 76 93 89.20 4 9964533 林FHc 98 90 78 87 89.20 5 9946535 張KXz 86 88 78 94 89.00 6 ... Stu ID name hwk mid quiz fin 學期成績 名次 9972291 錢JMe 73 69 74 1 43.10 81435 9958987 吳YLx 87 60 67 0 42.10 81436 9991053 簡LDy 71 62 78 2 41.40 81437 9965642 章EDu 73 64 76 0 41.40 81438 9941175 簡GUn 76 59 79 0 40.80 81439 ...Now Sorting according to student ID... ...Sorting done in 0.06200 seconds. === Now already sorted in Student_ID at ascending order. 9917001 簡KRe 70 81 62 69 72.10 63090 9917002 簡RVt 81 78 75 74 76.70 26950 9917003 吳NBa 83 83 67 75 78.20 16685 9917004 陳LKe 64 79 84 69 72.50 60506 9917005 林XLr 74 73 72 76 74.30 46350 9917006 林BDe 78 75 75 67 72.40 61277 ... Stu ID name hwk mid quiz fin 學期成績 名次 9998435 章LUs 77 78 75 83 79.50 9821 9998436 蔡NOm 70 77 74 79 76.10 31404 9998437 蔡HNj 69 83 74 77 76.90 25316 9998438 張KHj 72 84 66 76 76.60 27623 9998439 陳FHa 69 71 70 66 68.50 77766 === 用gen333.c生的資料是常態分佈, 不是 Uniform 分布! N= 81439, Average= 74.99, STD 標準差= 3.859 ==> 站在巨人肩膀上: 本程式這次是叫用函數 qsort2, Sort 81439 筆資料依成績遞減 Descending 用了平均 0.06179 秒. Hint: 用 rand( )%32767/32767.0 生出 12 個數加總, 然後減去6.0; 這樣就是 N(0, 1)的常態分配亂數; 把這亂數乘以你要的標準差, 再加上你希望的平均數; .. 這樣, 就會是你希望的常態分佈成績! Sorting 1000 times in 61.78600 seconds : function qsort2 used. 五都選舉已結束, 幾家歡樂幾家幹; 太陽依舊很燦爛, 輸贏已定賣靠餐。 選舉結果放兩邊, 作業練習擺中間; 若真想要不被當, 習題必須多多練! .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?! Hit ENTER key... D:\test> D:\test> gcc -DRUN=100 -DQSORT hwk13tq2.c D:\test> a.exe D:\test> gcc -DRUN=100 -DQQSORT hwk13tq2.c qqsort.c D:\test> a.exe D:\test> gcc -DRUN=100 hwk13tq2.c D:\test> gcc -DRUN=100 hwk13tq2.c qsort2.c D:\test> a.exe D:\test> gcc -DQSORT hwk13tq2.c D:\test> a.exe D:\test> gcc -DQQSORT hwk13tq2.c D:\test> gcc -DQQSORT hwk13tq2.c qqsort.c qsort2.c D:\test> gcc -DQQSORT hwk13tq2.c qqsort.c D:\test> gcc hwk13tq2.c qsort2.c qqsort.c ***************************************************/