text: /*
  The sample C++ quicksort file
  
  by nyLiao, May, 2019
  */
  
  #include <iostream>
  
  void quicksort(int a[], int l, int r);
  int  partition(int a[], int l, int r);
  void swap(int *x, int *y);
  
  
  int main(int argc, const char * argv[]) {
      int a[50] = { 24,  23,  22,  21,  20,  19,  18,  17,  16,  15,\
                    14,  13,  12,  11,  10,   9,   8,   7,   6,   5,\
                     4,   3,   2,   1,   0,  -1,  -2,  -3,  -4,  -5,\
                    -6,  -7,  -8,  -9, -10, -11, -12, -13, -14, -15,\
                   -16, -17, -18, -19, -20, -21, -22, -23, -24, -25 };
  
      quickSort(a, 0, 49);
      return 0;
  }
  
  
  void quicksort(int a[], int l, int r) {
      if (l < r) {
          int q = partition(a, l, r);
          quickSort(a, l, q-1);
          quickSort(a, q+1, r);
      }
  }
  
  
  void swap(int *x, int *y) {
      int tmp = *x;
      *x = *y;
      *y = tmp;
  }
  
  
  int partition(int a[], int l, int r) {
      int x = a[r];
      int i = l - 1;
  
      for (int j=l; j<r; j++) {
          if (a[j] <= x) {
              i++;
              swap(&a[i], &a[j]);
          }
      }
      i++;
      swap(&a[i], &a[r]);
  
      return i;
  }
  