//myqsort.cpp  -- demostration of quick sort, using template function
//CopyLeft by tsaiwn@csie.nctu.edu.tw
#include<iostream.h>
template<class GG> void swap(GG& x, GG& y){ GG t=x; x=y; y=t; }
template<class GG>
void myqsort(GG x[], int left, int right) {
   int i=left, j=right, flag= -1;
   while(i < j) {
      if(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++;
   }
   if(left+1 < i) myqsort(x, left, i-1);     /* 左邊多於 1 個 */
   if(i+1 < right) myqsort(x, i+1, right);   /* 右邊多於 1 個 */
}
long m[ ] = { 77, 85, 82, 55, 66, 96, 79, 73, 94 };
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<class YY>
void print(YY x[], int n) {
   cout << x[0];
   for(int i=1; i< n; ++i) {
      if(i%5 == 0 ) cout << endl;     /* 5 elements per line */
      else cout << ", ";
      cout << x[i];
   }
   cout << endl;
}
int main( ) {
   cout << "Before sort:\n"; print(m, nofm);
   myqsort(m, 0, nofm-1);
   cout << "After sort:\n";
   print(m, nofm);
   cout << "------" << endl;
   cout << "Before sort:\n"; print(y, nofy);
   myqsort(y, 0, nofy-1);
   cout << "After sort:\n";
   print(y, nofy);
}