/**
 *  file :  SelectionSort.java
 *
 *  desc :  Implementation of the SelectionSort algorithm
 *          on integer arrays.
 */


public class SelectionSort {

  /**
   *   post:  elements of A are sorted so that
   *
   *             A[0] <= A[1] <= ... <= A[A.length-1]
   */
  public static void sort( int[] A ) {
    int i;
    for( i = A.length-1; i > 0; i-- ) {

      /* outer loop invariant:  A[i..n-1] is sorted */

      // find maximum value in A[0..i]
      int maxIndex = 0;
      int j;
      for( j = 1; j < i; j++ ) {
	 
	/* inner loop invariant: for all k < j, A[maxIndex] >= A[k] */

	if( A[j] > A[maxIndex] )
	  maxIndex = j;
      }

      /* swap largest (A[maxIndex]) into A[i] to maintain invariant */
      swap( A, i, maxIndex );
    }
  }

  /**
   *   pre :  0 <= i <= A.length - 1
   *          0 <= j <= A.length - 1
   *
   *  post :  A[i] and A[j] are swapped
   */
  private static void swap( int A[], int i, int j ) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
  }
}

// eof