//myqsort2.cpp  -- demostration of quick sort, using template function
// another version which implemented in different way
//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, j=right+1, flag= -1;     /* 注意 i 和 j 的初值 */
   while(i < j) {
           /* 本例子要把 array x[] 由小到大排 */
      do{ i++; } while(x[i] < pivot);
      do{ --j; } while(x[j] > pivot);
      if(i< j) swap(x[i], x[j]);
   }
   // now the j-th position is the correct position for the pivot element
   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, 85, 99, 84, 55, 55 };
int nofm = (sizeof(m) / sizeof(long) );
double y[ ] = { 82.25, 94.25, 73.25, 77.25, 66.25, 82.25,
        55.25, 96.25, 79.25, 99.25};
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);
}