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

// burton rosenberg
// March 15, 1997

// Inputs an array of integers, uses quick sort
// to sort the integers.

/* The format of the input file is one integer per line, the
   first line giving the number of integers following.
   For example:

4
-9
3
2
17

*/

const int VERBOSE = 0 ;

void swap( int A[], int i, int j ) {

// interchanges value of A[i] with that of A[j]

   int t ; // t stands for temporary
   t = A[i] ;
   A[i] = A[j] ;
   A[j] = t ;
   return ;
}

void quickSort( int A[], int m, int n ) {

   int l, r, pivot ;

   if ( n-m < 2 ) return ;

   // Loop Invariant:
   //   m <= l <= r <= n 
   //   for all i in [m,l], A[i] <= pivot
   //   for all i in (r, n), A[i] > pivot


   // establish L.I.
   l = m ;
   r = n-1 ;
   pivot = A[m] ;
   
   while ( l<r ) {
      if ( A[l+1] <= pivot ) 
         l++ ;
      else if ( A[r] > pivot )
         r-- ;
      else
         swap( A, l+1, r ) ;
      // L.I. restored
   } 
   // move pivot into place
   swap( A, l /* ==r */, m ) ;


   // recurse on unsorted array partitions
   quickSort( A, m, l ) ;
   quickSort( A, l+1, n ) ;

   return ;
}

void main() {
   
   const int MAXSIZE = 20000 ;
   int arrayToSort[MAXSIZE] ;
   char * inputFileName = "input.dat" ;
   int numOfIntegers ;
   int i ;

   ifstream inFile ;

   inFile.open( inputFileName ) ;
   if ( !inFile ) {
      cout << "Could not open file " << inputFileName << "\n" ;
      return ;
   }

   inFile >> numOfIntegers ;
   if ( numOfIntegers > MAXSIZE ) {
      cout << "Too many integers. " << MAXSIZE << " is the maximum.\n" ;
      return ;
   }

   for ( i=0; i<numOfIntegers; i++ ) {
      inFile >> arrayToSort[i] ;
   }

   inFile.close() ;

   if ( VERBOSE ) { 
      cout << "Input\n-----" << endl ; 
      for ( i=0; i<numOfIntegers; i++ ) {
         cout << arrayToSort[i] << endl ;
      }
   }

   cout << "Sorting "  << numOfIntegers << " integers." << endl ;
   quickSort( arrayToSort, 0, numOfIntegers ) ;

   cout << "Checking." << endl ;
   for ( i=1; i< numOfIntegers ; i++ ) {
      if ( arrayToSort[i] < arrayToSort[i-1] ) {
         cout << "Error at index " << i << endl ;
         return ;
      }
   }

   if ( VERBOSE ) {
      cout << "\nOutput\n------" << endl ; 
      for ( i=0; i< numOfIntegers; i++ ) {
         cout << arrayToSort[i] << endl ;
      }
   }

}