import java.util.ArrayList;
import java.util.Collections;

/**
 * A collection of static sorting routines.
 *   @author Dave Reed
 *   @version 8/15/17
 */
public class Sorts {

  /**
   * Performs insertion sort on a list of Comparable items.
   *   @param items the list to be sorted (in place)
   */
  public static <T extends Comparable<? super T>> void insertionSort(ArrayList<T> items) {
    for (int i = 1; i < items.size(); i++) {        // for each index i,
      T itemToPlace = items.get(i);                 //   save the value at index i
      int j = i;                                    //   starting at index i,
      while (j > 0 && itemToPlace.compareTo(items.get(j-1)) < 0) {
          items.set(j, items.get(j-1));             //     shift values to the right
          j--;                                      //     until find spot for the value
      }
      items.set(j, itemToPlace);                    //   store the value in its spot
    }
  }
  
  /**
   * Performs selection sort on a list of Comparable items.
   *   @param items the list to be sorted (in place)
   */
  public static <T extends Comparable<? super T>> void selectionSort(ArrayList<T> items) {
    for (int i = 0; i < items.size()-1; i++) {    
        int indexOfSmallest = Sorts.findSmallestStartingAt(items, i);
        Collections.swap(items, i, indexOfSmallest);            
    }
  }
  
  private static <T extends Comparable<? super T>> int findSmallestStartingAt(ArrayList<T> items, int startIndex) {
      int indexOfMin = startIndex;                       
      for (int i = startIndex+1; i < items.size(); i++) {    
        if (items.get(i).compareTo(items.get(indexOfMin)) < 0) {
          indexOfMin = i;
        }
      }
      return indexOfMin;
  }
  
}