//qsort2.c  -- another version of quick sort, as qsort( ) in C Library
// @CopyLeft by tsaiwn@csie.nctu.edu.tw
// 這個版本與之前 qqsort 的寫法不太一樣, 但觀念相同!
// 可是, 這版本的寫法初學者比較難看懂
// 同樣是把最左邊那個元素當作pivot(樞紐元素)(一開始也有把最左與中間對調)
// 照 C Library qsort( )規定的參數, 所以 qsort2 用法與qsort完全相同
//        注意, 使用qsort2( )  之前要像以下這樣宣告:
void qsort2(void*x, int n, int size,
                int (*cmp)(const void*, const void*) );
// 通常我們可把上面宣告寫在 Header file .h 檔案內,
// 然後請  User 自己 #include  "該.h檔"
// 檔案用雙引號 "" 夾住是表示該.h檔在目前工作目錄先找找看,
///  .. 若找不到還是要去系統區找看看 ( 這時當作寫 <該.h檔> )
//  所以 #include "stdio.h"  通常是對的, 除非你目錄下有 stdio.h,
//  ..那會先抓你目錄下的 stdio.h, 當然若該檔案沒問題也是可以啦!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/// quick sort 有很多寫法, 這 qsort2 版本比較難看懂 ! !
static void * tmp; // points to temporary memory for swap data
   // 以下故意用"static" 使得 myqsort( ) 只有在這檔案內才看得見它 !
   // 還有, 因為 C++ 不允許對 void* 運算, 所以轉型(cast)為 char*
static void mySwap(char*y, int sz, int i, int k) { // y[i] : y[k]
   memcpy(tmp, y+i*sz, sz);     //  tmp = y[i]
   memcpy(y+i*sz, y+k*sz, sz);  // y[i] = y[k];
   memcpy(y+k*sz, tmp, sz);     // y[k] = tmp;
}// mySwap(   寫成 function 方便在 myqsort( ) 內使用.
  // 注意, 以下的 myqsort( ) 不是要給使用者直接用的!
static void myqsort(char*x, int sz, int left, int right,
                     int (*comp)(const void*, const void*) ) {
   int mid, i = left, j = right+1;   // 注意 j
   void* pivot_p;
   // int flag = 1;  //  這版本不必用到 Flag
   // 先把中間那個與最左邊對調, 因最左當 pivot 比較好寫!
   // pivot 樞紐元素就是在這回合(pass)會被丟到定位的元素
   mid = (left + right)/2;
   mySwap(x, sz,  left, mid); // 把最左那個 與 中間那個 交換..
   j = right + 1;  // 因等下是用 do { j--; } while( ...
   // partition 分割; 原則: 指著 pivot 的(i 或 j)不要動, 另一個要動
   pivot_p = x + left*sz;
   while(i < j) {  // 還沒走過頭ㄝ, 就每次 x[i] 與 x[j] 比
       //do { ++i; }while(i<j && x[i] < x[left]);   // Ascending
       //do { j--; }while( x[j] > x[left]);   // Ascending
       do { ++i; }while(i<j && comp(x+i*sz, pivot_p) < 0);
         // 注意上句我們利用 "short cut evaluation" 若 i>=j 就不做了
       do { j--; }while( comp(x+j*sz, pivot_p) > 0);  // 一直跳過大的
       if(i< j) {   //  swap(x[i], x[j]);   // 還沒走過頭 !
           mySwap(x, sz,  i, j);   // 我i不要的跟你j不要的交換 :-)
       } // if
   } // while
   // now the j-th position is the correct 位置 for the pivot element  
   // 注意 j 是 pivot 應該在的位置! 但是我們寫法 pivot 就是 x[left]
   mySwap(x, sz,  left, j);   // swap(x[left], x[j]); 
   // 注意這樣後,  pivot 已經在 j-th 位置; j-th 那個會被換到 left 處
   if(left < j-1) myqsort(x, sz, left, j-1,comp); // 左邊多於 1 個
   if(j+1 < right) myqsort(x, sz, j+1, right, comp); // 右邊多於 1 個
} //myqsort(
///  *** 以下提供與 C Library 的 qsort( ) 一樣的介面(interface)
//  *** 根據規定, void* 可以接受任何指標或address, 所以用 void*x
void qsort2(void*x, int n, int element_size,
                    int (*compare)(const void*, const void*) ) {
    tmp = malloc(element_size);  // 要一個臨時記憶體來給交換時用
       // 但是照  C++ 規定, void* 不可運算, char* 才可以做運算 
       // 所以把 x 轉型 (cast) 為 char* 後傳過去給 myqsort( )
    myqsort((char*)x, element_size, 0, n-1, compare);
}// qsort2(
/// gcc -c qsort2.c   (這會生出機器碼檔案 qsort2.o)
/// 然後你要用就   gcc yourfile.c qsort2.o
/// 
/***** 如果你還是看不太懂, 請看以下用中文寫的 pseudo code (虛擬碼)
     //假設你要把 x[left], x[left+1], ... x[right] 這些由小到大排好 
 void myqsort(char*x, int sz, int left, int right, 比較函數 comp) {
   /// Step_1: 先做 partition (分割), 要切割為左右兩半,
     //   注意, 這裡說的"半"不一定剛好一半! 運氣差可能一邊是 0 個!
     //   若一邊是 0 個, 就是所謂的 "Worst case"  (何時?)
     //左半要都比基準元素小, 右半要都比基準元素大!
     // 阿當然基準元素要在左半與右半之間
    i = left;   // i 指到  x[left];
    j = right + 1;   // j 指到  x[right] 那個的右邊一格; // 注意!!
    // 因為要把 x[left] 當作基準(pivot; 樞紐)元素,
    // 為了避免發生 worst case, 先把它跟中間那個對調!
    //  這樣做是萬一要 sort 的是已經排好, 那就從worst case變太爽了!
    mid = (left+right)/2;
    swap x[left] 與 x[mid];
    while( i < j) {  // i 與 j 由左右兩邊往中間移動
       repeat{ i++; } until 看到 x[i] 比 x[left] 大就停
       repeat{ --j; } until 看到 x[j] 比 x[left] 小就停
       // 左邊的不該比 x[left] 大 !  右邊的不該比 x[left] 小!!!
       if( i < j) {  // 防呆一下
          swap x[i] 與 x[j];   // 就是要左邊的小, 右邊的大
       } // if
       // 換了之後, i 指著那個仍比 x[left]小, j 指著那個仍比 x[left]大
       // 注意都是跟 x[left] 比喔, 因它是我們的基準(pivot; 樞紐)元素
       // ..接著會再繞回 while(i < j) 的頭部, 剛好可再做那兩個 repeat
    } // while
    // 這時候 i >= j 所以會到這來
    // 因為先把 i 往右邊移, 再把 j 往左邊移, 所以..
    //  所以這時 j 指著那個比 x[left] 小! 但那個的右邊都比 x[left]大
    swap x[left] 與 x[j] ;  // 把 pivot 丟到 j 指的位置
    // 這時候 j 指著那個(pivot)的左邊都比 pivot 小; 右邊都比 pivot 大
    // 所以只要把左半排好, 把右半也排好, 那就大功告成!
  /// Step_2: recursive sorting the left part and the right part
    // 因此, 只要各半有2個或更多個, 就 recursive 叫自己來 sort :
    if(left < j-1) myqsort(x, sz, left, j-1,comp); // 左邊多於 1 個
    if(j+1 < right) myqsort(x, sz, j+1, right, comp); // 右邊多於 1 個
    // 注意, 左半是從 x[left], .. 到 x[j-1] 
    //   右邊那半則是 從 x[j+1] 開始, 到 x[right] 止
 } //  myqsort(
********************/