/***************************************************************
Author:	        Dr. Daniel Spiegel, Updated by: Trisha Badlu
Creation Date:  21 March 2017
Due Date:       31 March 2017
Assignment:     #3
Filename:       SortSearch.h
Course: 	CSC136 - 020
Professor Name: Dr. Spiegel
Purpose:        Creates a template class that helps to compute
	        results on any element type, as opposed to a
	        specific type.
***************************************************************/
// FILE: SortSearch.h
// A couple of things that are nice to have available

// SORTS AN ARRAY (ASCENDING ORDER) USING SELECTION SORT ALGORITHM
//    USES exchange AND find_index_of_min
/***************************************************************
Function name: exchange (mutator)
Description: Swaps two elements
Parameters: eltType& - x (import/export)
		       y (import/export)
Return Value: none
***************************************************************/
   // EXCHANGES TWO INTEGER VALUES
   template <class eltType> void exchange(eltType &x,eltType &y)
   // Arguments:
   // Both: INOUT:
   {	eltType temp;
		temp=y; y=x; x=temp;
   }
/***************************************************************
Function name: selSort (facilitator)
Description: Sorts the elements in a list using selection sort
Parameters: eltType - *list (import/export)
		      items (import)
Return Value: none
***************************************************************/
template <class eltType> void selSort(eltType *list,int items)
// Arguments:
// list: INOUT - array to be sorted;
// items IN: number of items to be sorted (items >= 0)

// Sorts the data in array items (list[0] through list[items-1]).
// Pre:  list is defined and items <= declared size of actual argument array.
// Post: The values in list[0] through list[items-1] are in increasing order.
{
   // Local data ...
   int idxMax;  // subscript of each smallest item located by find_index_of_min

   for (int spot = items-1; spot > 0; spot--)
   {
      // Invariant: The elements in list[spot+1] through list[items-1] are in their
      //    proper place and spot > 0.

      // Find index of largest unsorted element
      idxMax = spot;
      for (int idx = 0 ; idx < spot ; idx++)
		if (list[idx] > list[idxMax])
			idxMax = idx;

      // Exchange items at position idxMax and spot if different
      if (spot != idxMax)
		exchange (list[idxMax], list[spot]);
   }  // end for

}  // end sel_sort

/***************************************************************
Function name: orderedSearch (facilitator)
Description: Searches for an item in the array
Parameters: eltType - *list (import/export)
		      items (import)
		      key (import)
Return Value: int - index
***************************************************************/
// Templated Search function
template <class eltType>
		int orderedSearch(eltType *list,int items,eltType key)
{
	int index;
	for (index=0;index<items && list[index]<key;index++);
 if (index==items || list[index]>key) return(-1);
 return(index);
}