public class InsertionSort
3: import java.util.Scanner;
5: /**
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class InsertionSort {
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: + "Insertion Sort\n"
19: + "==============\n\n"
20: + "This program counts how many operations it takes "
21: + "for insertion sort to sort a\nreversed array "
22: + "of various sizes, "
23: + "and compares that result to the expected value\n"
24: + "of N^2 + N - 2.");
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 = 1; i <= HOW_MANY; ++i) {
32: // create an array of random integers
33: ++len;
34: int[] numbers = makeReversedArray(len);
36: // sort it
37: int result = insertionSort(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 insertion 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 insertionSort(int[] arr) {
69: int count = 0;
70: for (int i = 0; i < arr.length - 1; ++i) {
71: int p = i + 1;
72: ++count;
73: int temp = arr[p];
74: while (p > 0 && (++count > 0) && arr[p - 1] > temp) {
75: ++count;
76: arr[p] = arr[p - 1];
77: --p;
78: }
79: ++count;
80: arr[p] = temp;
81: }
82: return count;
83: }
85: /**
86: * Swap two array elements
87: *
88: * @param arr the array to swap elements of
89: * @param one one index to swap to/from
90: * @param other other index to swap to/from
91: * @return the number of array operations (assignments)
92: */
93: private static int swap(int[] arr, int one, int other) {
94: if (one != other) {
95: int temp = arr[one];
96: arr[one] = arr[other];
97: arr[other] = temp;
98: return 3; // three assignments
99: } else {
100: return 0;
101: }
102: }
104: /**
105: * Calcuilate how many operations we'd expect for insertion sort in the worst
106: * case.
107: *
108: * @param len the length of the list
109: * @return the expected number of operations for insertion-sorting a list of
110: * the given length
111: */
112: private static int expected(int len) {
113: return len * len + len - 2;
114: }
116: /**
117: * Ask the user if they'd like to continue.
118: *
119: * @return true if the user wants to continue; false otherwise
120: */
121: private static boolean userContinue() {
122: System.out.print("\nPress ENTER to continue or N or Q to quit: ");
123: return KBD.nextLine().isEmpty();
124: }
126: }