Comp 271 Midterm Study Guide Answers to Additional Problems


1. Recall that Insertion Sort sorts an N-element array as follows:
    for (k=0; k<N; k++) {
          Precondition: A[0]..A[k-1] are sorted
          insert x=A[k] into the correct position among A[0]..A[k-1]
          Postcondition: A[0]..A[k] are now sorted

Do this for k=0,1,2,3 for the array A= [13, 47, 2, 16, 35, 14, 11, 38 ]

After 1 pass: Well, we shouldn't even do the k=0 pass; any one-element list is automatically sorted.
After 2 passes:    [13, 47, 2, 16, 35, 14, 11, 38]
After 3 passes:    [2, 13, 47, 16, 35, 14, 11, 38]
After 4 passes:    [2, 13, 16, 47, 35, 14, 11, 38]


2. Recall that Selection Sort sorts an N-element array as follows:
    for (k=0; k<N-1; k++)
       Pre: A[0]..A[k-1] are sorted and are smaller than any subsequent elements
       Find the smallest among A[k]..A[N-1]
       Swap it into position k
       Post: A[0]..A[k] are sorted and are smaller than any subsequent elements

Do this for k=0,1,2,3 for the array A = [13, 47, 2, 16, 35, 14, 11, 38 ]

After 1 pass:       [2, 47, 13, 16, 35, 14, 11, 38]
After 2 passes:   [2, 11, 13, 16, 35, 14, 47, 38]
After 3 passes:   [2, 11, 13, 16, 35, 14, 47, 38]      no swapping!
After 4 passes:   [2, 11, 13, 14, 35, 16, 47, 38]


3. Here is Bailey's partition code for QuickSort. The partitioning value is originally at data[left].

private static int partition(int data[], int left, int right) {
// pre: left <= right
// post: data[left] placed in the correct (returned) location
    while (true)  {     
        while (left < right && data[left] < data[right]) right--;        // move right "pointer" toward left
        if (left < right) swap(data,left++,right);
        else return left;
       
        while (left < right && data[left] < data[right]) left++;        // move left pointer toward right
        if (left < right) swap(data,left,right--);
        else return right;
    }
}

Use this to partition the array [13, 47, 2, 16, 35, 14, 11, 38 ], with left=0 (left end) and right=7 (right end).
You can do this by following the code step-by-step, but it is a lot more efficient to "understand" what it is doing.


Pass 1, 1st half:      [11, 47, 2, 16, 35, 14, 13, 38 ]     
Pass 1, 2nd half:    [11, 13, 2, 16, 35, 14, 47, 38 ]     

Pass 2, 1st half:      [11, 2, 13, 16, 35, 14, 47, 38 ]


4. Merge these two lists into one sorted list:

    [2, 6, 19, 21, 47, 83, 87, 90, 95, 97 ]
    [3, 5, 12, 17, 31, 38, 48, 51, 88 ]

[2, 3, 5, 6, 12, 17, 19, 21, 31, 38, 47, 48, 51, 83, 87, 88, 90, 95, 97]


5. Suppose we have a linked list of Cells,
    private class Cell {String data; Cell next; Cell(String d, Cell n) {data=d; next = n};
                String getData() {return data;}     String getNext() {return next;}   }

Suppose the variable p of type Cell is a pointer to the first cell.

(a). Write a loop to count the number of Cells in the list.

    int count = 0;
    while (p!=null) {
          count++;
          p = p.next();
    }

(b). Write java statements to insert a new cell containing the string "breadfruit" immediately after the cell pointed to by p.

I should have said that you can assume p!=null; ie, p does in fact point to a cell!

       Cell newcell = new Cell("breadfruit", p.next());
       p.setNext(newcell);


6. The main efficiency difference between ArrayLists and LinkedLists of size N is that accessing the kth element of an ArrayList is O(1) (that is, a constant that does not depend on k or N), while accessing the kth element of a LinkedList is O(N) (for a randomly chosen k, averaging N/2). For inserting, on the other hand, these are reversed (though inserting at a given position in a LinkedList is only O(1) if we have already got a pointer to the preceding Cell).

All of InsertionSort, SelectionSort, QuickSort, and MergeSort can be ported to LinkedList objects. Which, if any, new implementation would likely be subject to a significant performance hit in doing so?

InsertionSort, SelectionSort, and MergeSort all work well for linked lists, although we would need to keep various intermediate pointers on Cells in the list of interest. All these methods move neatly through the list in sequential order.

Quicksort is a little harder. First, there is the need to move backwards in the first half of the partition loop in #3 above, involving right--. Having a doubly-linked list would improve things here. The second part is the recursive call, now with two Cell pointers marking the subrange. Again, a doubly linked list would make this workable.