public class BubbleSort
1: /**
2: *
3: * @author Mark Young (A00000000)
4: */
5: public class BubbleSort {
6:
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: + "Bubble 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:
31: // print title
32: System.out.println("\n"
33: + "Sorting Strings\n"
34: + "---------------\n");
35:
36: // show sorting
37: System.out.println("Before sorting:\n\t" + names);
38: bubbleSort(names);
39: System.out.println("After sorting:\n\t" + names);
40:
41: // report counts
42: int numAsgn = names.getNumAsgn();
43: int numComp = names.getNumComp();
44: System.out.printf("To sort %,d words "
45: + "took %,d assignments "
46: + "and %,d comparisons,\n"
47: + "for a total of %,d operations.%n%n",
48: names.length, numAsgn, numComp, numAsgn + numComp);
50: System.out.printf("We expected Bubble sort to take %,d operations "
51: + "to sort %,d words.%n",
52: expect(names.length), names.length);
53: }
55: /**
56: * Sort a list of integer values, generated randomly.
57: *
58: * @param numbers the numbers to sort
59: */
60: public static void sortNumbers(SortArray<Integer> numbers) {
61: tracing = false;
62: System.out.println("\n"
63: + "Sorting Numbers\n"
64: + "---------------\n");
65:
66: bubbleSort(numbers);
67: int numAsgn = numbers.getNumAsgn();
68: int numComp = numbers.getNumComp();
69: System.out.printf("To sort %,d numbers "
70: + "took %,d assignments "
71: + "and %,d comparisons,\n"
72: + "for a total of %,d operations.%n%n",
73: HOW_MANY, numAsgn, numComp, numAsgn + numComp);
75: System.out.printf("We expected Bubble sort to take %,d operations "
76: + "to sort %,d numbers.%n",
77: expect(HOW_MANY), HOW_MANY);
78:
79: }
81: /**
82: * Perform bubble sort on the given array.
83: *
84: * @param <T>
85: * @param arr the array to sort.
86: */
87: public static <T extends Comparable<? super T>>
88: void bubbleSort(SortArray<T> arr) {
89: arr.reset();
90: for (int i = arr.length - 1; i > 0; --i) {
91: for (int j = 0; j < i; ++j) {
92: if (arr.compare(j, j + 1) > 0) {
93: arr.swap(j, j + 1);
94: }
95: }
96: if (tracing) {
97: System.out.println("one more bubbled up: " + arr);
98: }
99: }
100: }
102: /**
103: * Calculate how many operations a list of the given length should take.
104: *
105: * @param numItems the number of elements in a list.
106: * @return the number of operations expected (on average) to sort that list
107: */
108: private static int expect(int numItems) {
109: return (numItems * numItems + numItems) * 5 / 4;
110: }
111:
112: }