//bbsort.c  -- by tsaiwn@csie.nctu.edu.tw
// 氣泡排列法, 類似教官要把一列學生由低到高排好
// 或當過兵的:  班長要把一列班兵由低到高排好! (由小到大)
// 也可以說類似水中的氣泡一直往上冒
/// 所以, 才稱為 Bubble sort (氣泡排列法)
/// 注意, 若沒使用 FLAG 提早結束則一般稱為鄰近比較交換法
/// 鄰近比較交換法: Sibling compare and exchange sort
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define N_MAX 32
#define DATA_MIN 38
#define DATA_MAX 568
void printArray(int *x, int n) {  // n data in x[ ]
  int i;
  for(i = 0; i < n; i++) {
     fprintf(stdout, "%d", x[i]);
     if(i%10 == 9) fprintf(stdout, "\n");  // 每10個
     else if(i == n-1) fprintf(stdout, "\n"); //最後一個
     else fprintf(stdout, ", ");
  } // for i
}//printArray( 
void bubbleSort(int x[ ], int n) { //氣泡排列法 Bubble sort
  // Bubble sort method, sort n records in array int x[ ];
  int i, k, flag;  // flag 用來指出是否已經排好, 不必再做了!
  int tmp;
  for(i = 0; i < n; i++) {  
    flag = 0; // assume already sorted
    for(k = 0; k < n-1; k++)
      if(x[k] > x[k+1]) {  // 左邊比較大就對調; x[k] < x[k+1]
        tmp = x[k+1]; x[k+1] = x[k]; x[k] = tmp; // swap
        flag = 1;   // 有對調, 不知道是否排好了 !
      } // if
    if(flag == 0) break; // already sorted! done !
  } // for ; 注意 flag == 0 表示這趟沒有發生對調的事 !
}// bubbleSort( 
/// ///
int main() {
  int * yy; // used to hold data
  int i, k, nRecord;
  // set Seed for rand() to force true random
  srand(time(0)); // Randomize
  fprintf(stderr, "Demo Buble Sort ... Generating data ...");
  nRecord = 12 + rand( ) % (N_MAX - 12+1);   // 12..N_MAX
  yy = malloc( nRecord * sizeof(int) ); // yy[nRecord];
  ///
  for(i = 0; i < nRecord; ++i)
     yy[i] = DATA_MIN + rand() % (DATA_MAX - DATA_MIN + 1); 
  //
  fprintf(stderr, " %d data generated.\n", nRecord);
  fprintf(stdout, "\nBefore Sort\n--- ---\n");
  printArray(yy, nRecord);  
   ///
  bubbleSort(yy, nRecord);
   ///
  fprintf(stdout, "\nAfter Sort\n--- --- ---\n");
  printArray(yy, nRecord); 
  fprintf(stderr, "\nHit ENTER key...");
  getchar( ); return 0;
} // main(
/******
Demo Buble Sort ... Generating data ... 28 data generated.

Before Sort
--- ---
139, 562, 223, 493, 513, 372, 48, 137, 399, 292
305, 129, 136, 150, 398, 471, 407, 306, 40, 368
556, 500, 166, 518, 461, 232, 95, 74

After Sort
--- --- ---
40, 48, 74, 95, 129, 136, 137, 139, 150, 166
223, 232, 292, 305, 306, 368, 372, 398, 399, 407
461, 471, 493, 500, 513, 518, 556, 562

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