#ifndef SELSORT_H
#define SELSORT_H

// Programmer: Brian Church     Class: CS 54
// file:       selSort.h	Date: 10/25/04
// Purpose:    Descending selection sort function and supporting functions

template<typename T>
unsigned int maxIndex(const T a[], 
                      const unsigned int sindex, 
                      const unsigned int eindex);

template<typename T>
void swap_vals(T& x, T& y);

// selSort(T [], usigned int)
// Descirption: Sort an array using the selection sort algorithm from
//              the Savitch text.
// Pre:   number_used is less than or equal to the size of the array.
// Post:  a[] is sorted in descending order.
template<typename T>
void selSort(T a[], const unsigned int number_used)
{
   unsigned int mi;
   for(unsigned int i = 0; i < number_used; i++)
   {
     mi = maxIndex(a, i, number_used);
     swap_vals(a[i], a[mi]); 
   }
   return;
}


// swap(T, T)
// Description: swap two values
// Pre: none
// Post: none
template<typename T>
void swap_vals(T& x, T& y)
{
   T temp = x;
   x = y;
   y = temp; 
   return;
}

// maxIndex(T [], const unsigned int, const unsigned int)
// Descirption: Find the index of the "biggest" element in the array within the
//              range sindex to eindex. 
// Pre:   sindex < eindex, sindex > -1, eindex is <= the size of the array, 
//        and the < operator is defined for T.
// Post:  The index of the "biggest" element in the range is returned. 
template<typename T>
unsigned int maxIndex(const T a[], 
                      const unsigned int sindex, 
                      const unsigned int eindex)
{
  unsigned int index_max = sindex;
  for(unsigned int i = sindex; i<eindex; i++)
  {
     if(a[index_max] < a[i])
        index_max = i;
  }
  return index_max;
}


#endif