/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
/**
 *  Sort an array of <CODE>Object</CODE>s using Selection Sort.  This
 *  is an O(n^2) sort.
 *
 *  @version 1.1 1999.11.27
 *  @author Russel Winder
 */
public class SelectionSort {
  /**
   *  The sort operation.
   *
   *  @param a the array to be sorted.
   *  @param c the <CODE>Comparator</CODE> used to compare the
   *  <CODE>Object</CODE>s during the sort process.
   */ 
  public static void sort(final Object[] a, final Comparator c) {
    for (int i = a.length-1 ; i > 0 ; --i) {
      //  Find the next (maximum or minimum depending on the order
      //  relation) value from that part of the array that is as yet
      //  unsorted.  This is the value to put in the current location
      //  of interest.
      int indexOfValue = 0 ;
      Object value = a[indexOfValue] ;
      for (int j = 1 ; j <= i ; ++j) {
        if (c.relation(value, a[j])) {
          value = a[j] ;
          indexOfValue = j ;
        }
      }
      //  Exchange the value in the current location of interest with
      //  the "maximum" value from the rest of the unsorted array.
      //  This increases by one the part of the array that is now
      //  fully sorted.
      if (indexOfValue != i) {
        a[indexOfValue] = a[i] ;
        a[i] = value ;
      }
    }
  }
}