public class BubbleSort
3: import java.util.Scanner;
5: /**
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class BubbleSort {
11: private static final Scanner KBD = new Scanner(System.in);
12: private static final int HOW_MANY = 10;
13: private static final int MAX = 1000;
14: private static int traceLevel = 0;
16: public static void main(String[] args) {
17: System.out.println("\n\n"
18: + "Bubble Sort\n"
19: + "===========\n\n"
20: + "This program counts how many operations it takes "
21: + "for bubble sort to sort a\nreversed array "
22: + "of various sizes, "
23: + "and compares that result to the expected value\n"
24: + "of 2N^2 - 2N.");
26: int len = 0;
27: do {
28: System.out.println();
29: System.out.printf("%10s %10s %10s%n",
30: "Length", "Operations", "Expected");
31: for (int i = 0; i < 10; ++i) {
32: // create an array of random integers
33: ++len;
34: int[] numbers = makeReversedArray(len);
36: // sort it
37: int result = bubbleSort(numbers);
39: // report operation count
40: System.out.printf("%10d %10d %10d%n",
41: len, result, expected(len));
42: }
43: } while (userContinue());
44:
45: }
47: /**
48: * Make an array of the given length, with the numbers 1 .. {@code length}
49: * in reverse order. This is the worst case for sorting for many methods.
50: *
51: * @param length the length of the array to create
52: * @return an array containing the numbers from {@code length} down to 1
53: */
54: private static int[] makeReversedArray(int length) {
55: int[] result = new int[length];
56: for (int i = 0; i < length; ++i) {
57: result[i] = length - i;
58: }
59: return result;
60: }
62: /**
63: * Perform bubble sort on the given array.
64: *
65: * @param arr the array to sort
66: * @return the number of array operations (comparisons and assignments)
67: */
68: public static int bubbleSort(int[] arr) {
69: int count = 0;
70: for (int i = arr.length - 1; i > 0; --i) {
71: for (int j = 0; j < i; ++j) {
72: ++count;
73: if (arr[j] > arr[j + 1]) {
74: count += swap(arr, j, j + 1);
75: }
76: }
77: }
78: return count;
79: }
81: /**
82: * Swap two array elements
83: *
84: * @param arr the array to swap elements of
85: * @param one one index to swap to/from
86: * @param other other index to swap to/from
87: * @return the number of array operations (assignments)
88: */
89: private static int swap(int[] arr, int one, int other) {
90: if (one != other) {
91: int temp = arr[one];
92: arr[one] = arr[other];
93: arr[other] = temp;
94: return 3; // three assignments
95: } else {
96: return 0;
97: }
98: }
100: /**
101: * Calcuilate how many operations we'd expect for bubble sort in the worst
102: * case.
103: *
104: * @param len the length of the list
105: * @return the expected number of operations for bubble-sorting a list of
106: * the given length
107: */
108: private static int expected(int len) {
109: return 2 * (len * len - len);
110: }
112: /**
113: * Ask the user if they'd like to continue.
114: *
115: * @return true if the user wants to continue; false otherwise
116: */
117: private static boolean userContinue() {
118: System.out.print("\nPress ENTER to continue or N or Q to quit: ");
119: return KBD.nextLine().isEmpty();
120: }
122: }