Problem Set 2 FAQ

Problem 1

For problem 1, could you define more precisely what constitutes a “pass” or “phase” of each of the sorting algorithms?
- A pass of selection sort consists of a single iteration of the for loop in the selectionSort() method:
```
public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) {
        int j = indexSmallest(arr, i, arr.length-1);
        swap(arr, i, j);
    }
}
```
- A pass of insertion sort consists of a single iteration of the outer for loop in the insertionSort() method:
```
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // statements inside outer for loop omitted
    }
}
```
- A “phase” of Shell sort in the sense used in problem 1 is a single iteration of the outer while loop that controls the sequence of increments. For problem 1, we are interested in the initial iteration of this loop (the “phase” in which incr equals 3):
```
while (incr >= 1) {
    // statements omitted
    incr = incr/2;
}
```
- A pass of bubble sort is a single iteration of the outer for loop in the bubbleSort() method:
```
public static void bubbleSort(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        // statements inside outer loop omitted
    }
}
```
- A “pass” of radix sort is the complete process of distributing values into separate bins based on the value of the current element in the sequence (e.g., current digit, current character, etc.), and then reassembling them back together into the original array after distribution.
- To get a sense of the order in which the calls to merge() happen in mergesort, see the series of slides entitled “Tracing the Calls to Mergesort” in the sorting lecture notes.

Problem 2

For problem 2 (“counting comparisons”), do you want the exact number of comparisons performed by each algorithm, or a big-O expression for the number of comparisons?

You should give the exact number of comparisons that would be performed by each algorithm for an already-sorted array of length 5.

Problem 6

coming soon

Problem 8

For problem 8, you mention that we should use a merge-based approach. Does this mean that we should be dividing up the arrays and then merging them somehow, as in mergesort?

Your approach should be based on the merge helper method used by mergesort, not on mergesort itself. The merge method uses indices to walk down the arrays and merge them; it doesn’t do any dividing up of the arrays. Your union method should also use indices to walk down the arrays, but it should form the intersection, rather than the merge.
I’m stuck on problem 8? Do you have any hints?

We strongly encourage you to consider one or more concrete cases on paper.

For example, consider the following arrays:
```
a1: {10, 5, 7, 5, 9, 4}
a2: {7, 5, 15, 7, 7, 9, 10}
```
Once you have sorted them, you will have the following:
```
a1: {4, 5, 5, 7, 9, 10}
a2: {5, 7, 7, 7, 9, 10, 15}
```
Then you will need to take an approach similar to the one taken by the merge method.

Like merge, you will need several different loops:
- one that executes as long as both arrays still have values
- one that takes care of any “leftover” values in a1
- one that takes care of any “leftover” values in a2
As the problem indicates, one key difference between merge and union is that merge needs to write all of the elements in both arrays to the results array, whereas you only want to write a value if it is unique. As a result, each of your three loops will need to include code that skips over duplicate values – i.e., values that have already been included in the results. And because there may be multiple duplicates of a given value in a given array, you will need to use nested loops to skip over the duplicates.

Try simulating on paper how you would process the above arrays. When should you increment each of your indices? When should you write a value to the results array?