/*************************************************************************
 *  Compilation:  javac ArraySort.java
 *
 *  Sort an array of elements of type Comparable.
 *
 *************************************************************************/


public class ArraySort {

   /**********************************************************************
    *  Helper functions
    **********************************************************************/
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }



   /**********************************************************************
    *  Selection sort
    *  Sedgewick Program 6.12
    **********************************************************************/
    public static void selectionsort(Comparable a[], int L, int R) {
        for (int i = L; i < R; i++) {
            int min = i;
            for (int j = i+1; j <= R; j++)
                if (less(a[j], a[min])) min = j;
            exch(a, i, min);
        } 
    }


   /**********************************************************************
    *  Insertion sort
    *  Sedgewick Program 6.13 without the sentinel
    **********************************************************************/
    public static void insertionsort(Comparable a[], int L, int R) {
        for (int i = L+1; i <= R; i++) {
            Comparable v = a[i];
            int j = i;
            while (j > L && less(v, a[j-1])) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = v;
        }
    }


}