package cse1030.test3; import java.util.List; /** * A utility class providing methods that process lists of integers. * * @author CSE1030_F13_14 * */ public class IntegerLists { /** * Returns the minimum integer in a non-empty list. * * @pre. t.size() > 0 * @param t * a list of Integer * @return the minimum integer in the list */ public static Integer minimum(List t) { // base case is a list of size 1 (because the precondition says // that we can assume that t is not empty) if (t.size() == 1) { // if there is only 1 element in the list then that // element is also the minimum (and maximum) return t.get(0); } // if the list has more than 1 element then the minimum // element is either the first element or the minimum in the // rest of the list Integer first = t.get(0); List rest = t.subList(1, t.size()); Integer min = Math.min(first, minimum(rest)); return min; } /** * Returns the index of the first occurrence of the specified integer in a * list of Integer, or -1 if the list does not contain the integer. * * @param i * the integer to search for * @param t * the list to search * @return the index of the first occurrence of i if * i is in the list, -1 otherwise */ public static int indexOf(Integer i, List t) { // a base case occurs if t is empty, in which case i is not in the list if (t.isEmpty()) { return -1; } // a second base occurs if the first element is equal to i Integer first = t.get(0); if (first.equals(i)) { // the index of the first element is zero return 0; } // this is the tricky part. At this point you can conclude that // i is not the first element of the list, so recursively call // indexOf (remembering that the base cases return either 0 or -1). // If the recursive call results in -1, then you know i is not // in the list, and you must return -1. If you get back anything // else, then you have to add 1 to the result because the recursive // call occurred after you concluded that i was not the first element // (i.e., it was at least the second element, which has index 1). List rest = t.subList(1, t.size()); int idx = indexOf(i, rest); if (idx == -1) { return -1; } return 1 + idx; } /** * Sorts a list of integer by recursively moving the smallest element of the * list to the front of the list. * * @param t * the list to sort */ public static void sort(List t) { // base case occurs with a list of size 0 or 1 (already sorted) if (t.size() < 2) { return; // i.e., do nothing to t because t is already sorted } // now just follow the steps in the test description // 1. find the minimum element m in the list Integer m = minimum(t); // 2. find the index of m in the list int idx = indexOf(m, t); // 3. swap the first element of the list and m Integer first = t.get(0); t.set(0, m); t.set(idx, first); // 4. recursively sort the rest of the list List rest = t.subList(1, t.size()); sort(rest); } }