//myqsort0.c  -- demostration of quick sort, C version
//CopyLeft by tsaiwn@csie.nctu.edu.tw
#include<stdio.h>
void swap(long* x, long* y){ long t=*x; *x=*y; *y=t; }
void myqsort222(double x[], int left, int right);
void myqsort(long 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]);
         //int 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, 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) );
void print(long x[], int n) { int i;
   printf("%ld", x[0]);  // cout << x[0];
   for(i=1; i< n; ++i) {
      if(i%5 == 0 ) 
         printf("\n");  // cout << endl;   /* 5 elements per line */
      else printf(", ");  // cout << ", ";
      printf("%ld", x[i]);  // cout << x[i];
   }
   printf("\n");  // cout << endl;
}
void print222(double x[ ], int);
int main( ) {
   printf("Before sort:\n");
      // cout << "Before sort:\n"; print(m, nofm);
   print(m, nofm);
   myqsort(m, 0, nofm-1);
   printf("After sort:\n");
      // cout << "After sort:\n";
   print(m, nofm);
   printf("------\n");  // cout << "------" << endl;
   printf("Before sort:\n");
      // cout << "Before sort:\n"; print(y, nofy);
   print222(y, nofy);
   myqsort222(y, 0, nofy-1);
   printf("After sort:\n");
      // cout << "After sort:\n";
   print222(y, nofy);
}
void print222(double x[], int n) { int i;
   printf("%f", x[0]);  // cout << x[0];
   for(i=1; i< n; ++i) {
      if(i%5 == 0 ) 
         printf("\n");  // cout << endl;   /* 5 elements per line */
      else printf(", ");  // cout << ", ";
      printf("%f", x[i]);  // cout << x[i];
   }
   printf("\n");  // cout << endl;
}
void myqsort222(double x[], int left, int right) {
   double t;
   int i=left, j=right, flag= -1;
   while(i < j) {
      if(x[i] > x[j]) {       /* 由小到大排 */
         // /// /// swap222(&x[i], &x[j]);
         t = x[i]; x[i]=x[j]; x[j]=t;   /* 這樣也可以 */
         flag = - flag;
      }
      if(flag<0) --j;  else i++;
   }
   if(left+1 < i) myqsort222(x, left, i-1);     /* 左邊多於 1 個 */
   if(i+1 < right) myqsort222(x, i+1, right);   /* 右邊多於 1 個 */
}