Chapter 2: Getting Started

Question 1

Insertion Sort

Answer 1

• Good for a small number of elements
• Starts at second element, then checks left to see if it is smaller than any elements to it’s left. If so, they switch positions. The third element then goes through the same process, and so on.
• The algorithm sorts the input numbers in place: it rearranges the numbers within the array A, with at most a constant number of them stored outside the array at any time.

Question 2

Insertion Sort Java Code

Answer 2

// A is an array of ints

for (int j = 1; j < A.length; j++) {
         int key = A[j];
         int i = j - 1;
         while (i >= 0 &amp;&amp; A[i] > key) {
            A[i+1] = A[i];
            i = i - 1;
         }
         A[i+1] = key;
}

Question 3

We must show three things about a loop invariant:

Answer 3

Initialization (base case): It is true prior to the first iteration of the loop.

Maintenance (inductive step): If it is true before an iteration of the loop, it remains true before the
next iteration.

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Question 4

Analyzing an algorithm

Answer 4

Predicting the resources that the algorithm requires, usually most importantly the time it takes.

Question 5

Insertion Sort Pseudocode

Answer 5

for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1.. j-1].
    i = j - 1
    while i >0 and A[i] >key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

Question 6

Insertion Sort Efficiency

Answer 6

O(n^2)

Question 7

Merge Sort

Answer 7

Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.

Conquer: Sort the two subsequences recursively using merge sort.

Combine: Merge the two sorted subsequences to produce the sorted answer.

Question 8

Merge Sort Efficiency

Answer 8

O(nlgn)

Question 9

Merge Sort Pseudocode

Answer 9

There is a separate function just called Merge, which adds what are called sentinel elements, that are basically just always going to be bigger than any other elements. You could alternatively check if one of the subarrays is empty:

MERGE(A, p, q, r)

1     n_1 = q - p + 1
2    n_2 = r - q
3    let L[1...n_1 + 1] and R[1...n_2 + 1] be new arrays
4    for i = 1 to n_1
5        L[i] = A[p+i-1]
6    for j = 1 to n_2
7        R[j] = A[q+j]
8    L[n_1 + 1] = inf
9    R[n_2 + 1] = inf
10   i = 1
11    j = 1
12   for k = p to r
13       if L[i] <= R[j]
14           A[k] = L[i]
15           i = i + 1
16       else A[k] = R[j]
17           j = j + 1

Then Merge Sort uses it

MERGE-SORT(A, p, r)

1    if p < r
2       q = floor((p + r)/2)
3       MERGE-SORT(A, p, q)
4       MERGE-SORT(A, q+1, r)
5       MERGE(A, p, q, r)