import java.util.ArrayList;

/**
 * Class that contains static methods for sorting an ArrayList of comparable items.
 *   @author Dave Reed
 *   @version 9/11/07 
 */
public class Sorts {
    public static final int NUM_LETTERS = 26;    // letters that may appear in words
    
    /**
     * Sorts (in place) the items in the list using radix sort
     *   @param list the nonempty list of comparable items to be sorted (all the same length) 
     */
    public static void radixSort(ArrayList<String> list) {
        int wordLength = list.get(0).length();
        ListOfBuckets<String> buckets = new ListOfBuckets<String>(NUM_LETTERS+1);
        
        ArrayList<String> tempList = list;
        for (int i = wordLength-1; i >= 0; i--) {
            for (String str : tempList) {
                buckets.add(str.charAt(i)-'a', str);
            }
            tempList = buckets.asList();
            buckets.clear();
        }
        
        for (int i = 0; i < list.size(); i++) {
            list.set(i, tempList.get(i));
        }
    }
    
    /**
     * Sorts (in place) the items in the list using selection sort
     *   @param list the list of comparable items to be sorted
     */
    public static void selectionSort(ArrayList<String> list) {
        
        for (int i = 0; i < list.size()-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < list.size(); j++) {
                if (list.get(minIndex).compareTo(list.get(j)) > 0) {
                    minIndex = j;
                }
            }
            String temp = list.get(minIndex);
            list.set(minIndex, list.get(i));
            list.set(i, temp);
        }
    }
}