//selsort.c  -- by tsaiwn@csie.nctu.edu.tw 
// 選擇排序法, 類似在書架上要把書排成由高而低或由低而高!
// 選出最高的, 然後跟最左(第0本)對調, ... (由高而低)
/// 注意本例子中已經修改為 資料 "好像" 是去要來的 getData( )
// 還有還有, 本例子的 selectionSort( ) 有三個參數,
// .. 第三個參數是一個函數, 就是說你要傳個 compare 函數給它,
// .. 它每次要比大小就會 call 你給它的 compare function,
// .. 這觀念叫做 call back function!
// 這樣, 只要換 compare function, 同樣的 sort 就會排成不同順序!
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define N_MAX 88 
int getData(int x[ ]);  // 參數中的 array 其實是指標 !
void printArray(int *x, int n);  // 參數中指標與 array 互通 !
void selectionSort(int x[ ], int n, int(*)(int,int) ); //注意!
int myComp(int a, int b), myComp22(int a, int b);
/// 宣告後立刻寫(定義)主程式
int main( ) {
   int * yy; // used to hold data, will points to Heap Area
   int i, k, nRecord;
   // 先自己跟系統要到足夠的空間, 然後 yy 指過去當作 array 用
   yy = (int*)malloc( N_MAX * sizeof(int) ); // yy[N_MAX];
   nRecord = getData(yy);
   fprintf(stderr, "Demo Selection Sort ... getting data ...");
   ///
   fprintf(stderr, " got %d data.\n", nRecord);
   fprintf(stdout, "\nBefore Sort 原始資料\n--- ---\n");
   printArray(yy, nRecord);  
   ///
   selectionSort(yy, nRecord, myComp);
   fprintf(stdout, "\nAfter Sort\n--- --- ---\n");
   printArray(yy, nRecord); 
   /// ///
   fprintf(stdout, "\nNow Sort with myComp22 ..");
   selectionSort(yy, nRecord, myComp22);
   fprintf(stdout, "\nAfter Sort with myComp22\n--- --- ---\n");
   printArray(yy, nRecord); 
   ///=== ===
   fprintf(stderr, "\nHit ENTER key...");
   getchar( ); return 0;
} // main(
/////////////////////////////////////////////////
void printArray(int *x, int n) {  // n data in x[ ]
  int i;
  for(i = 0; i < n; i++) {   // print x[0] .. x[n-1]
     fprintf(stdout, "%d", x[i]);
     if(i%10 == 9) fprintf(stdout, "\n");  // 每十個一列
     else if(i == n-1) fprintf(stdout, "\n");  //最後一個
     else fprintf(stdout, ", ");  // 中途就印逗號,
  } // for i
}//printArray(
int myComp(int a, int b) {  // a compare function for sort fn.
   if(a == b) return 0;
   if(a > b) return 1;
   return -1;   // a < b
} // 注意 qsort( ) 所需的 compare 函數是像這個喔 !
int myComp22(int a, int b) {  // another compare function
   if(a == b) return 0;
   if(a > b) return -1;   // 故意跟 myComp 相反 !
   return 1;   // a < b 故意回傳 1 假裝左邊大 :-)
} // 若叫這, 會 Ascending order 遞增排序
void selectionSort(int x[ ], int n, int(*comp)(int,int)) {
    //選擇排列法 Selection sort; this version is NOT a stable one
   // 參數內的 array 是騙人的, 其實是指標指到某處去看作 array
  // selection sort method, sort n records in array int x[ ];
  /// 注意第三個參數是個比較函數(compare function) 
  // call with myComp : Descending order 遞減
  // call with myComp22 : Ascending order 遞增排
  int i, k, max;
  int tmp;
  for(i = 0; i <= n-2; i++) {   // 0.. n-2
     max = i; // 假設我最大, 然後逐一找看看有沒比我大的
     for(k=i+1; k <= n-1; ++k) { // 從第 i+1 個開始找
        if(comp(x[k], x[max]) > 0) max = k; // comp 是傳入的 
     } // for( 找出最大的 ; 類似路上撿石頭方式 
     tmp = x[i];    //  swap(x[i], x[max]);  // step-2
     x[i] = x[max];   // .. 最大的跟第 i 個對調 !
     x[max] = tmp;   // ..若 comp 是故意顛到, 則 max 就是 min
  } // for i
  return; // done
} //selectionSort(
int getData(int x[ ]) {
    int i;
    static int y[ ] = { 88, 68, 58, 77, 92, 75, 95, 75, 55, 66, 57};
    const int NY = (sizeof y / sizeof y[0]);
    for(i=0; i < NY; i++) x[i] = y[i];   // memcpy ?
    return NY;
} //getData(
/************* Selection sort is NOT a stable sort. But ..
Selection sort can be implemented as a stable sort. 
If, rather than swapping in step 2, the minimum value is inserted
 into the first position (that is, all intervening items moved down),
 the algorithm is stable. However, this modification either requires
 a data structure that supports efficient insertions or deletions,
 such as a linked list, or it leads to performing Θ(n*n ) writes. 
Either way, it eliminates the main advantage of selection sort
 over insertion sort, which is always stable.

***********************************************

// stable version of selection Sort
void selectionStable(int x[ ], int n) { // stable Selection sort
  // selection sort method, sort n records in array int x[ ];
  // Ascending order 遞增, this version is a stable one :-)
  int i, k, min;
  int tmp;
  for(i = 0; i <= n-2; i++) {  // 0.. n-2
     min = i; // 假設我最小
     for(k=i+1; k <= n-1; ++k) { // 從第 i+1 個開始找
        if(x[k] < x[min]) min = k; // 有人比我小, 記住它
     }
     // step-2 insert that one into position i
     // move down all elemensts between x[i] and x[min-1]
     tmp = x[min];  // save the min one
     while(i < min) {   // 別寫錯, min 每次減一到 i 右邊為止
        x[min] = x[min-1];   // 例如 8--> 9,  7--> 8,  6--> 7, ...
        --min;
     }
     x[i] = tmp;  // 它該在這位置
  } // for i
  return; // done
}

*****************************/
/***************
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> gcc selsort.c
D:\test> a.exe
Demo Selection Sort ... getting data ... got 11 data.

Before Sort 原始資料
--- ---
88, 68, 58, 77, 92, 75, 95, 75, 55, 66
57

After Sort
--- --- ---
95, 92, 88, 77, 75, 75, 68, 66, 58, 57
55

Now Sort with myComp22 ..
After Sort with myComp22
--- --- ---
55, 57, 58, 66, 68, 75, 75, 77, 88, 92
95

Hit ENTER key...

*******************************************/