//qqsort.c  -- demostration of quick sort, as qsort( ) in C Library
// @CopyLeft by tsaiwn@csie.nctu.edu.tw
// 為避免碰到已經排序好的worst case, 一開始有把最左與中間對調
// 照 C Library qsort( )規定的參數, 所以 qqsort 用法與qsort完全相同
//        注意, 使用qqsort( )  之前要像以下這樣宣告:
///
void qqsort(void*x, int n, int size,
                int (*cmp)(const void*, const void*) );
// 可把上面這宣告寫在一個 Header file(.h 檔) 方便別人使用 !
// 當然也可以請要用的人自己在他程式打入上述宣告即可
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
///
/// quick sort 有很多寫法, 這版本是最容易看懂的! 但約慢10% :-)
///
static void * tmp; // points to temporary memory for swap data
   // 以下故意用"static" 使得 myqsort( ) 只有在這檔案內才看得見它 !
static void myqsort(char*x, int sz, int left, int right,
                    int (*comp)(const void*, const void*) ) {
   int mid, i=left, j=right;  // i 指向最左那個, j 指向最右那個
   int flag = 1;  // x[left] is the pivot; 1 means j 要過來
      // flag 用來指示要 i 往右動, 還是要 j 往左移動 ?
   // pivot 樞紐元素就是在這回合(pass)會被丟到定位的元素
   mid = (i+j)/2;   // 準備拿中間那個來當 pivot (樞紐)元素
   memcpy(tmp, x+i*sz, sz);    // 把最左那個 與 中間那個 交換..
   memcpy(x+i*sz, x+mid*sz, sz);   // x[i] = x[mid];
   memcpy(x+mid*sz, tmp, sz);     // x[mid] = tmp;
   // partition 分割; 就是經 n-1 次比較後切成兩半
   // 原則: 指著 pivot 的(i 或 j)不要動, 另一個要動
   while(i < j) {  // 還沒走過頭ㄝ, 就每次 x[i] 與 x[j] 比
      if(comp(x+i*sz, x+j*sz) > 0) {  //會排成 Ascending 由小到大排
         memcpy(tmp, x+i*sz, sz);    // 我i不要的跟你j不要的交換..
         memcpy(x+i*sz, x+j*sz, sz);  // .. tmp 是臨時記憶區
         memcpy(x+j*sz, tmp, sz);
            // ..把 x[i] 與 x[j] 對調; 注意 memcpy 是以 Byte 為單位 
         flag = -flag;  // 使的指著 pivot 的不會動 (i 動 ?  j 動?)
      } // if
      if(flag > 0) j--;  else  ++i;  // 不是那邊過來就是我過去 :-)
   }// while(
   // i-th 已經到達定位; 叫自己把左邊和右邊排好 ! 此時 i == j
   if(left+1 < i) myqsort(x, sz, left, i-1, comp); //左邊多於 1 個 
   if(i+1 < right) myqsort(x, sz, i+1, right, comp); //右邊多於 1 個 
} //myqsort(
///
/// *** 以下提供與 C Library 的 qsort( ) 一樣的介面(interface)
//   注意 tmp 是本檔案內的 Global 變數 (static Global)
void qqsort(void*x, int n, int size,
                   int (*compare)(const void*, const void*) ) {
    tmp = malloc(size);  // 要一個臨時記憶體來給交換時用
    myqsort((char*)x, size, 0, n-1, compare);  // sort x[0] .. x[n-1]
}// qqsort(  // 用法跟 C Library 的 qsort( ) 完全一樣
// 如何使用這:
///     gcc -c qqsort.c    (這會生出 qqsort.o )
/// 然後你要用就  gcc yourfile.c qqsort.o
/// 你的 yourfile.c 內要 #include "qqsort.h"
/****** 以下是 qqsort.h 內容; 若不 #include "qqsort.h"就自己寫宣告

//qqsort.h   @CopyLeft by tsaiwn@cs.nctu.edu.tw
#ifndef _QQSORT_H_
#define _QQSORT_H_

void qqsort(void*x, int n, int size,
           int (*cmp)(const void*, const void*));
#endif

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