//bbsAlg.c
//為了讓大家更容易了解 Bubble sort 演算法,
//    我把 bbsort.c 用更白話文方式解釋
//    用註解方式插入到 bbsortSort( ) 函數內 
// 注意喔, 原先在 e3.nctu 給大家的 bbsort.c 有個小 BUG 喔 !!
// 少做一個 pass  (就是 for i 少做一次! ) 
// 請看程式裡面的面註解說明 !  
// 通常測試不出來有Bug,  Why why WHY??? 


//bbsort.c  -- by tsaiwn@csie.nctu.edu.tw
// 氣泡排列法, 類似教官要把一列學生由低到高排好
// 或當過兵的:  班長要把一列班兵由低到高排好! (由小到大)
// 也可以說類似水中的氣泡一直往上冒
/// 所以, 才稱為 Bubble sort (氣泡排列法)
/// 注意, 若沒使用 FLAG 提早結束則一般稱為鄰近比較交換法
/// 鄰近比較交換法: Sibling compare and exchange sort
/// 
/////
/// 想一想, 這樣最多會比較(compare)幾次呢?
//  Pass 1:  n-1 個比較
//  Pass 2:  n-2 個比較
// ..
//  Pass n-1:  n-(n-1) = 1 個比較
//
/// So,  n-1 + (n-2) + ... +2 + 1 =  (n-1+1)*(n-1)/2
///  梯形面積 = (上底 + 下底) * 高 /2 =  n*(n-1)/2
///    == (n*n - n) /2
///  當 n 很大, 則 n 比 n*n 小很多可忽略不算 = n*n /2
/////  顯然 n*n /2 與 n 的平方成正比
///// 所以你會聽到 :
//////  Bubble sort 的 time complexity 是 Big O of n平方
//////   寫做 O(n*n)
///////////////////////////
 
 
void bubbleSort(int x[ ], int n) { //氣泡排列法 Bubble sort
  // Bubble sort method, sort n records in array int x[ ];
  //要排序的資料在 array x[0], x[1], ... x[n-1]
  int i, k, flag;  // flag 用來指出是否已經排好, 是就不必再做了!
  int tmp;   // 用來對調 (switch) 時的臨時變數 
  for(i = 1; i <= n-1; i++) {    // 做 n-1 趟 (pass)! 原來程式有 BUG!
            // 我放在 e3.nctu 的 bbsort.c 是寫 i < n -1  有 Bug!
            // 這樣會少做一趟, 但大部分不會有事 (與 data 有關)
            // 因通常不必做到最後一趟(pass; 回合)就已經排序好了 :-)
       // pass1 第 1 趟, pass 2 第二趟,... pass n-1 (最多這樣)
       // 例如 3 個資料則最多要走兩趟 ( 兩個 pass, 兩個回合)
     flag = 0; // assume already sorted; 0 = 這趟沒有鄰近的對調 
     for(k = 0; k < n-i; k++) {  // i = 1 時, 比到 x[n-2] : x[n-1]
          // 每趟都要從頭(k=0)比起, 每趟第一次都是 x[0] : x[1]
          // 每趟都只要走到 k = n-i-1 就可, 做 x[k] : x[k+1]
          // 因每走一趟(pass), 右邊就會多一個已經排好的!
          // 當然要寫成做到最後 ;k < n-2 ; 也可, 是白做的而已!
        if(x[k] > x[k+1]) {  // 左邊比較大就對調; x[k] < x[k+1]
             // 左大右小就來做對調, 這樣就會 Ascending 遞增排序 !
             // 鄰近兩個相比, 注意這Loop最後一次是 k = n-i-1
             // 當 i == 1 (第一趟), 最後一次就是 k = n-1-1 = n-2
             /// 最後一趟是 i = n-1 那趟!
             // 當 i == n-1, 最後一次就是 k = n-(n-1)-1 = 0
          tmp = x[k+1]; x[k+1] = x[k]; x[k] = tmp; // swap
          flag = 1;   // 有對調, 不知道是否排好了 ! 做記號!
        } // if
     }// for k  
     // 走完一趟, 若是都沒有對調(flag是0), 那表示再重新走也沒用!
     if(flag == 0) break; // already sorted! done !
  } // for i; 注意 flag == 0 表示這趟沒有發生對調的事 ! 
}// bubbleSort( 
/*****  ******
D:\test> path C:\Dev-Cpp\bin;%path%

D:\test> gcc bbsAlg.c
c:/Dev-Cpp/bin/../lib/gcc/mingw32/3.4.2/../../../libmingw32.a(main.o)(.text+0x10
6):main.c: undefined reference to `WinMain@16'
collect2: ld returned 1 exit status

D:\test> gcc -c bbsAlg.c

D:\test> dir bbs*
 磁碟區 D 中的磁碟沒有標籤。
 磁碟區序號:  F021-1832

 D:\memo\DOCUME~1\LABs\LAB-12 的目錄

2010/12/08  下午 07:20             3,582 bbsAlg.c
2010/12/08  下午 07:21               528 bbsAlg.o
               2 個檔案           4,110 位元組
               0 個目錄  68,911,251,456 位元組可用
******* ****** ****** ***/