package DataStructures;

/**
 * A class providing static array sorting routines
 * @see <a href="http://java.sun.com/products/j2se/1.4/docs/api/java/lang/Comparable.html">Comparable</a>
 * @author Peter Williams
 */

public class Sort {
    /**
     * This class is not to be instantiated
     */
    private Sort() {}

    /** 
     * Sorts an array <code>a[0..n-1]</code>
     * in ascending order using heapsort.  The array is
     * replaced on output by its sorted rearrangement.
     * Array elements must implement the Comparable interface 
     * in their defining class or in some superclass.
     *
     * @param a the array to sort 
     * @param <E> the type of elements held in the array 
     * @param n the number of elements sorted, elements
     * <code>a[n]</code> onwards are ignored
     *
     * @exception ArrayIndexOutOfBoundsException if <code>n</code> is
     * greater than the array length.
     */
    public static final <E extends Comparable<? super E>> 
				   void heapSort(E[] a, int n) {
	if (n < 2) {
	    return;
	}
	// build the heap
	for (int i = (n / 2) - 1; i >= 0; i--) {
	    demote(a, n, i);
	}
	// remove items successively from the top
	for (int i = n - 1; i > 0; i--) {
	    swap(a, i, 0);
	    demote(a, i, 0);
	}
    }

    /* private method to swap components a[i] and a[j] of an array */
    private static <E> void swap(E[] a, int i, int j) {
	E tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
    }

    /* private method to demote an item from heap[parent] to its
     * proper place in a heap, assuming both left and right sub-trees
     * are properly ordered heaps */
    private static <E extends Comparable<? super E>> 
			      void demote(E[] heap, int size, int parent) {
	E item = heap[parent];
	int child; 
	while ((child = (2 * parent) + 1) < size) {
	    // if there are two children, compare them
	    if (child + 1 < size && heap[child].compareTo(heap[child + 1]) < 0) {
		++child;
	    }
	    // compare item with the larger
	    if (item.compareTo(heap[child]) < 0) {
		heap[parent] = heap[child];
		parent = child;
	    } else {
		break;
	    }
	}
	heap[parent] = item;
    }

}