1
package sorting;
2
/** Stores a sequence of integers, and provides operations on them.
3
  *
4
  * @author David Lightfoot 2010-11-15, updated by Sharon Curtis 2011-06-09,
5
  *         further updated by (your student name and number here)
6
  */
7
public class Sequence {
8

9
    private static long stepCount = 0;
10

11
    public static void clearNumSteps() {
12
        stepCount = 0;
13
    }
14

15
    public static long getNumSteps() {
16
        return stepCount;
17
    }
18
    public final int max;
19
    public int[] a;
20

21
    public Sequence(int max) {
22
        a = new int[max];
23
        this.max = max;
24
    }
25

26
    // pre 0 <= i && i < max
27
    // a[i] == x
28
    public void insertAt(int i, int x) {
29
        a[i] = x;
30
    }
31

32
    public String toString() {
33
        String out = "";
34
        for (int elem : a) {
35
            out += elem + "\n";
36
        }
37
        return out;
38
    }
39

40
    public boolean isAscending() {
41
        int i = 1;
42
        while (i < max && a[i - 1] <= a[i]) {
43
            i++;
44
        }
45
        return i >= max;
46
    }
47

48
    // pre true
49
    // post a[0..size-1] is ascending
50
    void insertionSort() {
51
        int i = 1;
52
        int x;
53
        int j;
54
        while (i < a.length) {
55
            // a[0..i-1] is ascending
56
            // insert value at a[i] into correct position in a[0..i-1]
57
            j = i;
58
            x = a[i]; // x is the value originally at a[i]
59
            stepCount++; // counted: read a[i] into x
60
            // restructure the loop so we can count each element access
61
            while (j != 0) {
62
                // inspect a[j-1] to compare with x
63
                stepCount++; // counted: read a[j-1] for comparison
64
                if (a[j - 1] > x) {
65
                    // 'budge up' values that are bigger than x
66
                    // copying a[j-1] into a[j] performs a read of a[j-1] and a write to a[j]
67
                    a[j] = a[j - 1];
68
                    stepCount++; // counted: write to a[j]
69
                    stepCount++; // counted: read a[j-1] for the copy
70
                    j--;
71
                } else {
72
                    break;
73
                }
74
            }  // j == 0 OR a[j-1] <= x
75
            // 'drop in' x, the value that was at a[j]
76
            a[j] = x;
77
            stepCount++; // counted: write a[j] when inserting x
78
            i++; // advance to insert next value
79
        } // i >= a.length
80
    } // end of insertionSort
81

82
    void qSort(int low, int high) {
83
        int i = low, j = high, temp;
84
        int pivot = a[(low + high) / 2];
85
        stepCount++; // counted: read a[(low+high)/2] to initialise pivot
86

87
        while (i < j) {
88
            // move i forward while a[i] < pivot
89
            while (true) {
90
                stepCount++; // counted: read a[i] for comparison with pivot
91
                if (a[i] < pivot) {
92
                    i++;
93
                } else {
94
                    break;
95
                }
96
            }
97
            // move j backward while a[j] > pivot
98
            while (true) {
99
                stepCount++; // counted: read a[j] for comparison with pivot
100
                if (a[j] > pivot) {
101
                    j--;
102
                } else {
103
                    break;
104
                }
105
            }
106
            if (i <= j) {
107
                temp = a[i];
108
                stepCount++; // counted: read a[i] into temp for swap
109
                a[i] = a[j];
110
                stepCount++; // counted: read a[j] for the swap into a[i]
111
                stepCount++; // counted: write to a[i] during swap
112
                a[j] = temp;
113
                stepCount++; // counted: write to a[j] during swap
114
                i++;
115
                j--;
116
            }
117
        }
118
        if (low < j) {
119
            qSort(low, j); // recursive call
120
        }
121
        if (i < high) {
122
            qSort(i, high); // recursive call
123
        }
124
    } // end of insertionSort
125

126
    // pre true
127
    // post a[0..size-1] is ascending
128
    void quickSort() {
129
        qSort(0, max - 1);
130
    } // end of QSort
131
}

1
package sorting;
2

3
import java.util.*; // this package provides random number generating facilities
4

5
/** This class contains some code
6
  *
7
  * @author David Lightfoot 2010-11-15, updated by Sharon Curtis 2011-06-09,
8
  *         further updated by (your student name and number here)
9
  */
10
public class SortExplore {
11

12
    public static void main(String[] args) {
13

14
        int numElements = 20000; // edit this to change number of elements in array
15

16
        // first to set up a sequence with random numbers
17
        Random generator = new Random();
18
        Sequence s = new Sequence(numElements);
19
        for (int i = 0; i < numElements; i++) {
20
            s.insertAt(i, generator.nextInt());
21
        }
22

23
        Sequence oldS = new Sequence(numElements); // will hold original sequence
24
        // now to make oldS a copy of s
25
        for (int i = 0; i < numElements; i++) {
26
            oldS.a[i] = s.a[i];
27
        }
28

29

30

31
        System.out.println("Before sorting by Insertion Sort");
32
        System.out.println("sequence is ascending?:  " + s.isAscending());
33
        // System.out.println(s);
34
        Sequence.clearNumSteps();
35
        System.out.println("STARTING Insertion Sort");
36
        s.insertionSort();
37
        System.out.println("Insertion Sort done");
38

39
        System.out.println("After sorting by Insertion Sort ");
40
        System.out.println("sequence is ascending?:  " + s.isAscending());
41
        System.out.println("Number of steps is: " + Sequence.getNumSteps());
42
        // Now sort the already-sorted sequence again and count afresh
43
        Sequence.clearNumSteps();
44
        System.out.println("STARTING Insertion Sort on already-sorted sequence");
45
        s.insertionSort();
46
        System.out.println("Insertion Sort (2nd run) done");
47
        System.out.println("After 2nd run by Insertion Sort ");
48
        System.out.println("sequence is ascending?:  " + s.isAscending());
49
        System.out.println("Number of steps (2nd run) is: " + Sequence.getNumSteps());
50
        //  System.out.println(s);
51

52

53
        Sequence.clearNumSteps();
54
        System.out.println("Restoring unsorted sequence ");
55
        for (int i = 0; i < numElements; i++) { // restoring original s
56
            s.a[i] = oldS.a[i];
57
        }
58
        System.out.println("STARTING QuickSort");
59
        s.quickSort();
60
        System.out.println("QuickSort done");
61

62
        System.out.println("After sorting by QuickSort ");
63
        System.out.println("sequence is ascending?:  " + s.isAscending());
64
        System.out.println("Number of steps is: " + Sequence.getNumSteps());
65
        // Now sort the already-sorted sequence again and count afresh
66
        Sequence.clearNumSteps();
67
        System.out.println("STARTING QuickSort on already-sorted sequence");
68
        s.quickSort();
69
        System.out.println("QuickSort (2nd run) done");
70
        System.out.println("After 2nd run by QuickSort ");
71
        System.out.println("sequence is ascending?:  " + s.isAscending());
72
        System.out.println("Number of steps (2nd run) is: " + Sequence.getNumSteps());
73
    }
74
}
75

76
/*
77
Actual output from a run with numElements = 20 (captured when running the program):
78

79
Before sorting by Insertion Sort
80
sequence is ascending?:  false
81
STARTING Insertion Sort
82
Insertion Sort done
83
After sorting by Insertion Sort
84
sequence is ascending?:  true
85
Number of steps is: 419
86
STARTING Insertion Sort on already-sorted sequence
87
Insertion Sort (2nd run) done
88
After 2nd run by Insertion Sort
89
sequence is ascending?:  true
90
Number of steps (2nd run) is: 57
91
Restoring unsorted sequence
92
STARTING QuickSort
93
QuickSort done
94
After sorting by QuickSort
95
sequence is ascending?:  true
96
Number of steps is: 256
97
STARTING QuickSort on already-sorted sequence
98
QuickSort (2nd run) done
99
After 2nd run by QuickSort
100
sequence is ascending?:  true
101
Number of steps (2nd run) is: 138
102

103
Brief comments / analysis:
104
- Which is quicker (in terms of the number of accesses)? For this random 20-element run,
105
  QuickSort required 256 accesses on the first run vs Insertion Sort's 419, so QuickSort
106
  performed fewer array accesses on the unsorted data and is therefore quicker in this metric.
107
- What difference does it make the second time round? Insertion Sort on an already-sorted
108
  array performed much less work (57 accesses) because its inner loop rarely shifts elements;
109
  it inspects each element once and does few or no writes. QuickSort still performed partitioning
110
  and recursive work on the sorted input (138 accesses), so it did more work on the second run
111
  than Insertion Sort did.
112
- Why? Insertion Sort runs in O(n) for already-sorted input: each element requires a single
113
  comparison and no shifting, so accesses are minimal. QuickSort's cost depends on pivot selection
114
  and partitioning: even with a middle pivot it still performs comparisons across partitions and
115
  recursive calls, so it does not reduce to O(n) merely because the input is sorted.
116

117
Note: These numbers vary between runs because the sequence is randomly generated; different random
118
inputs (and different sizes) will change absolute counts. The relative behavior, however, is typical:
119
QuickSort tends to be more efficient on large, random data (roughly O(n log n) average) while
120
Insertion Sort can be extremely fast on nearly-sorted inputs (O(n)).
121
*/

1
package sorting;
2

3
/** Small test harness for Sequence.insertionSort to verify step counting. */
4
public class TestSequence {
5
    public static void main(String[] args) {
6
        Sequence s = new Sequence(5);
7
        s.insertAt(0, 5);
8
        s.insertAt(1, 3);
9
        s.insertAt(2, 4);
10
        s.insertAt(3, 1);
11
        s.insertAt(4, 2);
12

13
        Sequence.clearNumSteps();
14
        s.insertionSort();
15

16
        System.out.println("Sorted? " + s.isAscending());
17
        System.out.println("Steps: " + Sequence.getNumSteps());
18
        System.out.println("Array:\n" + s.toString());
19
    }
20
}