/* Sorts.java        Authors: Koffman & Wolz
 * Contains method selectionSort() to sort Comparable[] arrays.
 * Part of package psJava.
 */
package psJava;

public class Sorts {

  // precondition: array x is defined
  // postcondition: elements in array x are in increasing order
  public static void selectionSort(Comparable[] x) {

    int posMin;       //index of next smallest element
    Comparable temp;  //temporary value for exchange

    for (int fill = 0; fill < x.length-1; fill++) {
       /* invariant:
        *   The elements in x[0] through x[fill-1] are in
        *   their proper place and fill < x.length is true.
        */
       //Find index of smallest element in subarray
       //  starting at element x[fill].
       posMin = findPosMin(x, fill);

       //Exchange elements with indices fill and posMin.
       if (posMin != fill) {
         temp = x[fill];
         x[fill] = x[posMin];
         x[posMin] = temp;
       }
    }
  }


  private static int findPosMin(Comparable[] x, int fill) {
    int posMinSoFar = fill;
    for (int i = fill + 1; i < x.length; i++) {
       if (x[i].compareTo(x[posMinSoFar]) < 0)
          posMinSoFar = i;
    }

    return posMinSoFar;
  }
}