/**
 * Several static methods from the Decrease & Conquer lecture.
 *   @author Dave Reed
 *   @version 8/29/24
 */
public class Decrease {
    
    /**
     * Implements insertion sort using recursion.
     * @param <T> the type of values in the array (must be Comparable)
     * @param items the array being sorted in place
     */
    public static <T extends Comparable<? super T>> 
           void insertionSortRec(T[] items) {
        Decrease.insertionSortRecHelper(items, items.length-1);
    }
    
    private static <T extends Comparable<? super T>> 
           void insertionSortRecHelper(T[] items, int lastIndex) {    
        if (lastIndex > 0) {
            Decrease.insertionSortRecHelper(items, lastIndex-1);
            T value = items[lastIndex];
            int j = lastIndex-1;
            while (j >= 0 && items[j].compareTo(value) > 0) {
                items[j+1] = items[j];
                j--;
            }
            items[j+1] = value;
        }
    }
    
    ////////////////////////////////////////////////////////////////////
    
    /**
     * Implements insertion sort using iteration.
     * @param <T> the type of values in the array (must be Comparable)
     * @param items the array being sorted in place
     */
    public static <T extends Comparable<? super T>> 
           void insertionSort(T[] items) {  
        for (int i = 1; i < items.length; i++) {
            T value = items[i];
            int j = i-1;
            while (j >= 0 && items[j].compareTo(value) > 0) {
                items[j+1] = items[j];
                j--;
            }
            items[j+1] = value;
        }
    }  
      
    ////////////////////////////////////////////////////////////////////
    
    /**
     * Implements the quick select algorithm for finding the kth order statistic.
     * @param <T> the type of values in the array (must be Comparable)
     * @param items the array being searched
     * @param k the desired value size (e.g., k=1 is smallest value, k=2 is next
     *          smallest value, ..., k=items.length is the largest value)
     * @return the kth largest value in items
     */
    public static <T extends Comparable<? super T>> 
           T quickSelect(T[] items, int k) {
        return Decrease.quickSelect(items, 0, items.length-1, k);
    }    
    
    private static <T extends Comparable<? super T>> 
           T quickSelect(T[] items, int left, int right, int k) {
        int pivotIndex = Decrease.partition(items, left, right);
        if (k == pivotIndex+1-left) {
            return items[pivotIndex];
        }
        else if (k < pivotIndex+1-left) {
            return Decrease.quickSelect(items, left, pivotIndex-1, k);
        }
        else {
            return Decrease.quickSelect(items, pivotIndex+1, 
                                        right, k-(pivotIndex-left+1));
        }
    }  
    
    private static <T extends Comparable<? super T>> 
           int partition(T[] items, int left, int right) {
        T pivot = items[left];
        int pivotIndex = left;
        for (int i = left+1; i <= right; i++) {
            if (items[i].compareTo(pivot) < 0) {
                pivotIndex++;
                T temp = items[pivotIndex];
                items[pivotIndex] = items[i];
                items[i] = temp;
            }
        }
        T temp = items[pivotIndex];
        items[pivotIndex] = items[left];
        items[left] = temp;
        return pivotIndex;
    }
    
    ///////////////////////////////////////////////////////////////////
 
    public static void main(String[] args) {
        Integer[] nums = {8, 3, 12, 5, 9, 10, 1, 2};
        Decrease.insertionSortRec(nums);
        for (int n : nums) {
            System.out.print(n + " ");
        }
        System.out.println();

        Integer[] nums1 = {8, 3, 12, 5, 9, 10, 1, 2};
        Decrease.insertionSort(nums1);
        for (int n : nums1) {
            System.out.print(n + " ");
        }
        System.out.println();        
        
        Integer[] nums2 = {8, 3, 12, 5, 9, 10, 1, 2};
        for (int k = 1; k <= nums2.length; k++) {
            System.out.println(Decrease.quickSelect(nums2, k));
        }
        
    }
}