//myqsort.cpp  -- demostration of quick sort, using template function
//@CopyLeft by tsaiwn@csie.nctu.edu.tw
//一個 template sorting function, 用在 sort 整數array, 也用在實數array!
#include<iostream>
using namespace std;
#include <stdio.h>
// 以下的 swap( ), 其實在 C++ 程式庫內已經有 swap( ) template 函數
// template<class GG> void swap(GG& x, GG& y){ GG t=x; x=y; y=t; }
/// 這邊故意寫三個 compare functions, 此範例中只會用到兩個
bool myLess(long a, long b) { return a < b; }
bool myLess(double a, double b) { return a < b; }
bool myLess(float a, float b) { return a < b; }
/// 也可寫一個template compare function 給 myQsort( ) 用就可!
/// template<class GG> bool myLess(GG a, GG b) { return a < b; }
template<class GG>
void myQsort(GG x[ ], int left, int right) {
   int i=left, j=right, flag= -1;
   while(i < j) {
      if( myLess(x[i], x[j]) ) {  // 由大到小排; 所以左小右大要對調 
         swap(x[i], x[j]);
         //GG t = x[i]; x[i]=x[j]; x[j]=t;   // 或是這樣也可以
         flag = - flag;
      }
      if(flag<0) --j;  else i++;  // 指著 pivot 者不可動!
   }
   if(left+1 < i) myQsort(x, left, i-1);     // 左邊多於 1 個 
   if(i+1 < right) myQsort(x, i+1, right);   // 右邊多於 1 個 
}//myQsort, recursive function
// 懶得輸入, 弄兩個 array 來測試 myqsort( ) 與 print( )
long m[ ] = { 77, 85, 82, 55, 66, 96, 79, 73, 94, 38, 88, 58, 55, 55};
int nofm = (sizeof(m) / sizeof(long) );
double y[ ] = { 82.5, 94.5, 73.5, 77.5, 66.5, 82.5, 55.5, 96.5, 79.5, 99.5};
int nofy = (sizeof(y) / sizeof(double) );
// 以下也是樣板函數(template function) to print out the array x[ ]
template<class YY>
void print(YY x[], int n) {   // YY is a type of somekind of data
   cout << x[0];   // 先印出最開始 x[0]
   for(int i=1; i< n; ++i) {
      if(i%5 == 0 ) cout << endl;     // 5 elements per line 
      else cout << ", ";
      cout << x[i];   // 不管 x[i] 是何種 type 都這樣寫!
   }
   cout << endl;  // 印出  NewLine "\n"
}//print(
int main( ) {
   cout << "Before sort m:\n"; print(m, nofm);
   myQsort(m, 0, nofm-1);   // array, 起點, 終點
   cout << "After sort m:\n";
   print(m, nofm);
   cout << "------" << endl;
   cout << "Before sort y:\n"; print(y, nofy);
   myQsort(y, 0, nofy-1);
   cout << "After sort y:\n";
   print(y, nofy);
}
/****** 請注意, quick sort is NOT stable, 但可以想辦法寫成 stable
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> g++ myqsort.cpp
D:\test> a.exe
Before sort m:
77, 85, 82, 55, 66
96, 79, 73, 94, 38
88, 58, 55, 55
After sort m:
96, 94, 88, 85, 82
79, 77, 73, 66, 58
55, 55, 55, 38
------
Before sort y:
82.5, 94.5, 73.5, 77.5, 66.5
82.5, 55.5, 96.5, 79.5, 99.5
After sort y:
99.5, 96.5, 94.5, 82.5, 82.5
79.5, 77.5, 73.5, 66.5, 55.5

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