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

// burton rosenberg
// March 15, 1997

// Inputs an array of integers, uses seletion 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

*/

// 0 for quiet, 1 for output.
const int VERBOSE = 0 ;

int findMinimum( int A[], int n ) {

// returns the integer i such that A[i] is minimum over all
// A[k] where k in [0,n).

   int nextToCheck, smallestSoFar ;

   if ( n<1 ) {
      return -1 ; // error.
   }

   nextToCheck = 1 ;
   smallestSoFar = 0 ;  

   // Loop Invariant:
   //   smallestSoFar in [0,nextToCheck) and
   //   for all k in [0,nextToCheck), A[k] >= A[smallestSoFar]. 

   // ASSERT LOOP INVARIANT
   while ( nextToCheck<n ) {

      if ( A[smallestSoFar] > A[nextToCheck] ) {
         smallestSoFar = nextToCheck ;
      }
      nextToCheck ++ ;    
      // ASSERT LOOP INVARIANT
   }
   return smallestSoFar ;
}

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 selectionSort( int A[], int n ) {

// selectionSorts array A of size n.

   int numSorted ;
   int i ;

   numSorted = 0 ;

   // Loop Invariant:
   //   The smallest numSorted values are
   //   sorted in descending order in locations [n-numSorted,n)
   //   and the rest are in locations [0,n-numSorted)

   // ASSERT LOOP INVARIANT
   while ( numSorted<n ) {
      i = findMinimum(A,n-numSorted) ;
      numSorted++ ;
      swap( A, i, n-numSorted ) ; 
      // ASSERT LOOP INVARIANT
   } 
   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 ;
   selectionSort( arrayToSort, 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 ;
      }
   }
}