package l22;

import l16.IntSorter;
import l17.GraphicalSorter;

/**
 * Insertion sort (maintain sorted prefix, insert each additional element)
 * 
 * In this standard version the "find position" and "insert" parts are merged by
 * scanning from the position of the element to be inserted rightwards, moving
 * larger elements forwards as necessary.
 *
 * @author Michael Albert,
 * @author Lech Szymanski
 *
 */
public class InsertionSort extends GraphicalSorter implements IntSorter {

    /** Default constructor for non-graphical sorting. */
    public InsertionSort() {
        this(0);
    }

    /** Designated initialiser.
     * 
     * @param visDelay Slows down visulisation (if 0  no visualisation)
     */
    public InsertionSort(int visDelay) {
        super(visDelay);
    }

    /**
     * Method that provides descriptive name
     * of the sorter.
     * 
     * @return String with the name of the sorting algorithm.
     */
    public String getName() {
        return "Insertion sort";
    }

    /**
     * Method that sorts an array of ints.
     * 
     * @param a The array to sort.
     */
    public void sort(int[] a) {
        super.show(a); /** Graphics call (nothing to do with sorting) */
        sort(a, 0, a.length);
        super.done(); /** Graphics call (nothing to do with sorting) */
    }

    /**
     * Insertion sort algoirthm.
     * 
     * @param a Array that is sorted
     * @param lo Starting index of the subarray to sort
     * @param hi End point of the subarray to sort
     */    
    public void sort(int[] a, int lo, int hi) {
        for (int i = lo; i < hi; i++) {
            findAndInsert(a, i, a[i]);
        }
    }

    /**
     * Finds the position of the value in the sorted subarray of a starting
     * at index 0 and up to index index-1.
     * 
     * @param a Array that is sorted
     * @param index The size of the subarray
     * @param value The value for which to find place in the subarray
     */        
    private void findAndInsert(int[] a, int index, int value) {
        index--;
        while (index >= 0 && a[index] > value) {
            a[index + 1] = a[index];
            index--;
            super.show(index); /** Graphics call (nothing to do with sorting)*/
        }
        a[index + 1] = value;
    }
}