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

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

   // EXCHANGES TWO INTEGER VALUES
   template<class T>
   void exchange
       (T&,			// INOUT: first item
         T& );			// INOUT: second item

template<class T>
void sel_sort
    (apvector <T>& items,	// INOUT: array to be sorted
      int n)				// IN: number of items to be sorted (n >= 0)

// Sorts the data in array items (items[0] through items[n-1]).
// Pre:  items is defined and n <= declared size of actual argument array.
// Post: The values in items[0] through items items[n-1] are in increasing
//          order.

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

   for (int i = 0; i <= n-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, n-1);

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

// FILE: FindMinT.h
template<class T>
int find_index_of_min
   (const apvector <T>& x,	// IN: array of elements
    int start_index,		// IN: subscript of
    int end_index)			// IN: number of elements to be checked

// Returns the subscript of the smallest element in the subarray.
// Returns -1 if the subarray bounds are invalid.
// Pre:  The subarray is defined and 0 <= start_index <= end_index.
// Post: x[min_index] is the smallest value in the array.
{
	// Local data ...
	int min_index;		// index of the smallest element found

	// Validate subarray bounds
	if ((start_index < 0) || (start_index > end_index))
	{
	   cerr << "Error in subarray bounds" << endl;
	   return -1;		// return error indicator
	}
	// Assume the first element of subarray is smallest and check the rest.
	// min_index will contain subscript of smallest examined so far.
	min_index = start_index;
	for (int i = start_index + 1; i <= end_index; i++)
	   if (x[i] < x[min_index])
	      min_index = i;

	// All elements are examined and min_index is
	//    the index of the smallest element.
	return min_index;                    // return result for valid subarray
} // end find_index_of_min

// FILE: ExchngT.h
// Exchanges two type T values
template<class T>
void exchange
    (T& element1, T& element2)
{
   T temp;
   temp = element1;
   element1 = element2;
   element2 = temp;
}