public class SelectionSort
1: /**
2: *
3: * @author Mark Young (A00000000)
4: */
5: public class SelectionSort {
7: private static boolean tracing = true;
8: private static final int HOW_MANY = 10000;
10: public static void main(String[] args) {
11: System.out.println("\n\n"
12: + "Selection Sort\n"
13: + "==============\n");
15: // Strings
16: sortNames(Common.getCrew());
18: // integers
19: sortNumbers(Common.randomNumbers(HOW_MANY, 1, HOW_MANY));
21: System.out.println();
22: }
24: /**
25: * Sort a list of words/names.
26: *
27: * @param names the names to sort
28: */
29: public static void sortNames(SortArray<String> names) {
30: // print title
31: System.out.println("\n"
32: + "Sorting Strings\n"
33: + "---------------\n");
35: // show sorting
36: System.out.println("Before sorting:\n\t" + names);
37: selectionSort(names);
38: System.out.println("After sorting:\n\t" + names);
40: // report counts
41: int numAsgn = names.getNumAsgn();
42: int numComp = names.getNumComp();
43: System.out.printf("To sort %,d words "
44: + "took %,d assignments "
45: + "and %,d comparisons,\n"
46: + "for a total of %,d operations.%n%n",
47: names.length, numAsgn, numComp, numAsgn + numComp);
49: System.out.printf("We expected Selection sort to take %,d operations "
50: + "to sort %,d words.%n",
51: expect(names.length), names.length);
52: }
54: /**
55: * Sort a list of integer values, generated randomly.
56: *
57: * @param numbers the numbers to sort
58: */
59: public static void sortNumbers(SortArray<Integer> numbers) {
60: tracing = false;
61: System.out.println("\n"
62: + "Sorting Numbers\n"
63: + "---------------\n");
65: selectionSort(numbers);
66: int numAsgn = numbers.getNumAsgn();
67: int numComp = numbers.getNumComp();
68: System.out.printf("To sort %,d numbers "
69: + "took %,d assignments "
70: + "and %,d comparisons,\n"
71: + "for a total of %,d operations.%n%n",
72: HOW_MANY, numAsgn, numComp, numAsgn + numComp);
74: System.out.printf("We expected Selection sort to take %,d operations "
75: + "to sort %,d numbers.%n",
76: expect(HOW_MANY), HOW_MANY);
78: }
80: /**
81: * Perform insertion sort on the given array.
82: *
83: * @param <T>
84: * @param arr the array to sort.
85: */
86: public static <T extends Comparable<? super T>>
87: void selectionSort(SortArray<T> arr) {
88: arr.reset();
89: for (int i = 0; i < arr.length - 1; ++i) {
90: int p = i;
91: for (int j = i+1; j < arr.length; ++j) {
92: if (arr.compare(j, p) < 0) {
93: p = j;
94: }
95: }
96: arr.swap(i, p);
97: if (tracing) {
98: System.out.println("one more selected: " + arr);
99: }
100: }
101: }
103: /**
104: * Calculate how many operations a list of the given length should take.
105: *
106: * @param numItems the number of elements in a list.
107: * @return the number of operations expected (on average) to sort that list
108: */
109: private static int expect(int numItems) {
110: return (numItems * numItems + 5 * numItems - 6) / 2;
111: }
113: }