//testqqsort.c -- test qqsort( ) -- 可以 sort 任何 array
// @CopyLeft by tsaiwn@cs.nctu.edu.tw
// 用簡單的 array 搭配 compare 函數來測試我們寫的 qqsort( )
// 請注意, 我們故意把 qqsort( ) 寫在另一個檔案 qqsort.c 內
// 所以, 要 gcc testqqsort.c qqsort.c 或在 IDE 內用 project
// 在 IDE 內只要開新 project, 把 testqqsort.c 和 qqsort.c 加入即可
/// 注意, 千萬不可以把 qqsort.h 也加入成員! 
/// 另外, 你可以把使用 qqsort( ) 直接改為用程式庫的 qsort( ) 
/// 然後再測試看看
#include <stdio.h>
#include "qqsort.h"
/*** ***
  qqsort.h 內就是以下宣告:
  void qqsort(void*x, int n, int size,
                int (*cmp)(const void*, const void*) );
***********/
int y[ ] = { 55, 66, 23, 38, 55, 69, 58, 49, 88, 20, 77 };
const int NY = (sizeof y / sizeof y[0]);
void print(int*x, int n) { int i;
   for(i=0; i<n;i++) printf("%d ", x[i]);
   printf("\n");
}
int comp(const void*, const void*);
int cmp22(const void*pa, const void*pb);
///
int main( ) {
   printf("Original data:\n ");
   print(y, NY); 
   qqsort(y, NY, sizeof(int), comp);
   printf("After sort...\n ");
   print(y, NY); 
   printf("AGAIN, sort it with cmp22:\n ");
   qqsort(y, NY, sizeof(int), cmp22);
   print(y, NY); 
   printf("Hit ENTER key...");
   getchar( ); return 0;
}// main(
int comp(const void*pa, const void*pb) {
   int* a = (int*)pa;
   int* b = (int*)pb;
   return *a - *b;
} // comp
int cmp22(const void*pa, const void*pb) {
   int* a = (int*)pa;
   int* b = (int*)pb;
   return *b - *a;
} // cmp22
/******
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> gcc testqqsort.c qqsort.c
D:\test> a.exe
Original data:
 55 66 23 38 55 69 58 49 88 20 77
After sort...
 20 23 38 49 55 55 58 66 69 77 88
AGAIN, sort it with cmp22:
 88 77 69 66 58 55 55 49 38 23 20
Hit ENTER key...

D:\test> linenum < qqsort.h
   01 //qqsort.h   @CopyLeft by tsaiwn@cs.nctu.edu.tw
   02 #ifndef _QQSORT_H_
   03 #define _QQSORT_H_
   04
   05 void qqsort(void*x, int n, int size,
   06            int (*cmp)(const void*, const void*));
   07 #endif

D:\test> type qqsort.c
//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 有很多寫法, 這版本是最容易看懂的!
///
static void * tmp; // points to temporary memory for swap data
   // 以下故意用"static" 使得 myqsort( ) 只有在這檔案內才看得見它 !
static void myqsort(void*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 變數
void qqsort(void*x, int n, int size,
                   int (*compare)(const void*, const void*) ) {
    tmp = malloc(size);  // 要一個臨時記憶體來給交換時用
    myqsort(x, size, 0, n-1, compare);  // sort x[0] .. x[n-1]
}// qqsort(  // 用法跟 C Library 的 qsort( ) 完全一樣
//
/// gcc -c qqsort.c
/// 然後你要用就  gcc yourfile.c qqsort.o

D:\test> 
********************/