package OldCode;

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

/**
 * A collection of static sorting routines.
 *   @author Dave Reed
 *   @version 9/10/15
 */
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++) {      // for each index i,
      int indexOfMin = i;                           //   find the ith smallest item
      for (int j = i+1; j < items.size(); j++) {    
        if (items.get(j).compareTo(items.get(indexOfMin)) < 0) {
          indexOfMin = j;
        }
      }
    
      T temp = items.get(i);                        //   swap the ith smallest
      items.set(i, items.get(indexOfMin));          //   item into position i
      items.set(indexOfMin, temp);              
    }
  }
  
}