//myqsort3.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) {
   GG pivot = x[left];
   int i=left+1, j=right, flag= -1;
   while(i <= j) {   /* 注意!  i==j 時還沒完成 */
           /* 本例子要把 array x[] 由小到大排 */
      while(x[i] <= pivot) i++;
      while(x[j] > pivot) --j;
      if(i< j) { swap(x[i], x[j]);   i++; }
   }
   swap(x[left], x[j]);   /* 注意 j 是 pivot 應該在的位置 */
   if(left < j-1) myqsort(x, left, j-1);     /* 左邊多於 1 個 */
   if(j+1 < right) myqsort(x, j+1, right);   /* 右邊多於 1 個 */
}
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<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);
}