/* FILE: quickSort.cpp   last change: 16-Mar-2001   author: Avancini Andrea
 */

#include <fstream.h>
#include <iostream.h>

const long int  MAX_INTEGERS = 1000;


void quicksort(double*, const long int, const long int);
inline void swap(double*, double*);

main(int argc, char** argv) {
  if (argc < 2 || argc > 3) {
     cerr << "syntax:" << endl
          << " > quicksort <file1>" << endl
          << "or" << endl
          << " > quicksort <file1> <file2>" << endl
          << "where, <file1> = input file of unordered numbers" << endl
          << "and, <file2> = output sorted file" << endl;
     exit(1);
  }

  ifstream  in;
  in.open(argv[1]);
  if (!in.good()) {
     cerr << "err: file " << argv[1] << " does not exist" << endl;
     exit(1);
  }

  double A[MAX_INTEGERS];
  long int n = 0;
  while (!in.eof()) {
     if (n++ > MAX_INTEGERS) {
        cerr << "err: file " << argv[1] << " contains more than "
             << MAX_INTEGERS << " integers." << endl;
        exit(1);
     }
     in >> A[n];
  }
  in.close();

  quicksort(A, 0, n-1);

  if (argc == 2)  for(long int i = 0; i < n; i++)  cout << A[i] << endl;
  else {
     ofstream  out;
     out.open(argv[2]);
     if (!out.good()) {
        cerr << "err: could not open file " << argv[2] << endl;
        exit(1);
     }
     for(long int i = 0; i < n; i++)  out << A[i] << endl;
     out.close();
  }
}


inline void swap(double* a, double* b) {
   double swap = *a;
   *a = *b;
   *b = swap;
}


void quicksort(double v[], const long int primo, const long int ultimo)  {
   if(primo < ultimo)  {
      long int p = primo;
      long int u = ultimo+1;
      double pivot = v[primo];
      do {
         while(v[++p] < pivot);
         while(v[--u] > pivot);
         if(p < u)  swap(&v[p],&v[u]);
      } while(p < u);
      swap(&v[primo],&v[u]);
      quicksort(v, primo, u-1);
      quicksort(v, u+1, ultimo);
   }
}