// FILE: SelSort.cpp
// SORTS AN ARRAY (ASCENDING ORDER) USING SELECTION SORT ALGORITHM
//    USES exchange AND find_index_of_min

#include "intxchng.cpp"
#include "intmin.cpp"

   // Local Functions ...
   // FINDS THE SUBSCRIPT OF THE SMALLEST VALUE IN A SUBARRAY
   int find_index_of_min
     (const apvector <int>&,	// IN: the array of elements
      int,				// IN: index of first subarray element
      int);				// IN: index of last subarray element

   // EXCHANGES TWO INTEGER VALUES
   void exchange
     (int&,				// INOUT: first item
      int&);				// INOUT: second item

void sel_sort
  (apvector <int>& items)	// INOUT: array to be sorted
 
// Sorts the data in array items (items[0] through items.length()-1).
// Pre:  items is defined. 
// Post: The values in items[0] through items[items.length()-1] are
//          in increasing order.

{
   // Local data ...
   int min_sub;		// subscript of each smallest item located by
				// find_index_of_min

   for (int i = 0; i < items.length() - 1; i++)
   {
       // Invariant: The elements in items[0] through items[i-1] are in their 
      //    proper place and i < n-1.

      // Find index of smallest element in unsorted section of items.
      min_sub = find_index_of_min (items, i, items.length() - 1);

      // Exchange items at position min_sub and i if different
      if (i != min_sub)
         exchange (items[min_sub], items[i]);
   }  // end for
}  // end sel_sort