/**
 * Yvonne's version of Selection sort.
 */

public class SelectionSort
  implements Sorter
{ 
   
  // +------------------+----------------------------------------
  // | Exported Methods |
  // +------------------+

    public Object[] sort(Object[] toSort, GComparator comp){
      //Find the smallest element and bring it to the front.
      // b is the index of the current smallest element. 
        
      for(int i = 0; i < toSort.length; i++){
        int b = findSmallest(toSort, i, comp);
      
        //swap the value at index b with the value at index i.
        // System.out.println("Swapping toSort[" + i + "]=" + toSort[i] +
        //                   " and toSort[" + b + "]=" + toSort[b]);
        Object temp = toSort[b];
        toSort[b] = toSort[i];
        toSort[i] = temp;
      } //for
      return toSort;
    }//sort (Object[])


    /**
     * Find the index of the smallest value in the array at hand, 
     * starting from index startIndex.
     */
    public int findSmallest(Object[] sorting, int startIndex, GComparator comp){
      // Assume the first thing is the smallest
      int guess = startIndex;
      // Look at everything else
      for(int i = startIndex+1; i < sorting.length; i++){
        // If the thing we're looking at is smaller, update the guess
        if(comp.mayPrecede(sorting[i], sorting[guess]))
          guess = i;
      }//for
      return guess;
    }//findSmallest(Object[])
} // class SelectionSort