///////    File quicksort.C    ///////
#include <iostream.h>
#include <stdlib.h>

void quicksort(int a[], int i, int j)
{ // sort a[i] to a[j] inclusive
  int partition(int a[], int, int); // prototype
      if ( i >= j )  return;
      int k = partition (a, i, j);  // k is  position of pe
      quicksort(a, i, k-1);         // sort left sub-array
      quicksort(a, k+1, j);         // sort right sub-array
}

inline void exchange(int b[], int i, int j)
{ //  array b is modified
  int t = b[j];
      b[j] = b[i]; b[i] = t;
}

int partition(int a[], int low, int high)
{ // partition a[low] through a[high]
  register int pe;
      int i = low;
      int j = high;
      // choose middle element as partition element
      exchange(a, (i+j)/2, j);
      pe = a[j];    // move pivot to right end
      while (i < j)
      {    while (i < j && a[i] <= pe) i++;
           while (i < j && a[j] >= pe) j--;
           if (i < j) exchange(a, i++, j);
      }
      if (i != high)
           exchange(a, i, high);  // pe to partition location 
      return(i);    // return index of partition element
}

int a[1000];

int main(int argc, char * argv[])
{ int i;
      int dim = atoi(argv[1]);
      for (i=0; i < dim; i++)
           a[i]=(23*i)%dim;
      quicksort(a,0,dim-1);
      cout << "sort done\n";
      for (i=0; i < dim; i++)
             cout << a[i] << " ";
      cout << endl;
      return(0);
}