/**
 * Implementation of the insertion sort algorithm.
 * @author Jeff Raab
 */
public class InsertionSort implements ISort {

    /** Returns the name of this sort algorithm. */
    public String getName() {
        return "Insertion Sort";
    }
    
    /**
     * Performs the selection sort algorithm 
     * on the given array of objects.
     * @param anArray array of objects to sort
     */
    public void sort(Comparable[] anArray) {
        if (anArray == null) {
            return;
        }
        
        for (int i = 1; i < anArray.length; i++) {
            insert(anArray, i);
        }
    }
    
    /**
     * Inserts the element at the given index 
     * into the proper location of the sorted array
     * in the range [0, i) in the given array.
     * @param anArray array of objects to sort
     * @param k index of object to insert
     */
    public void insert(Comparable[] anArray, int k) {
        if (k == 0) {
            return;
        }
        
        if (anArray[k].compareTo(anArray[k - 1]) < 0) {
            swap(anArray, k, k - 1);

            insert(anArray, k - 1);
        }
    }

    /**
     * Swaps the objects in the given array at the two given indices.
     * @param anArray array of objects to swap
     * @param i index of first object to swap
     * @param j index of second object to swap
     */
    private void swap(Comparable[] anArray, int i, int j) {
        Comparable temp = anArray[i];
        anArray[i] = anArray[j];
        anArray[j] = temp;
    }
}