**AP
Computer Science Sorting Test**

**0. (0 points) NAME________________________________________ PERIOD_________
**

__INSTRUCTIONS__

- Put your name on the test.
**Failure to do so will result in a loss of one point.**(Let's face it, if you don't know your name, you probably have bigger problems than this test.) - This test is
**closed book**. No computer, no friends, just you and the test. - Where possible,
**SHOW YOUR WORK!**I don’t know how to assign partial credit to the void. - Don't panic. It's just a test.

**1. (5 points in three parts)** Consider the following sorting method:

public static void mystery(int[] a) { for (int i = 1; i < a.length; i++) { int j = i; int current = a[i]; while (j > 0 && current < a[j-1]) { a[j] = a[j-1]; j--; } a[j] = current; } }

**1A. (1 point)** What is the name of this sorting method? (Circle the correct answer.)

Bubble SortInsertion SortSelection Sort Heap Sort Quick Sort Merge Sort

**1B. (3 points; 1 for order of growth, 2 points for explanation)** What is the order of growth of this sorting method? Explain why. (Let `n` be the number of elements in the array for the purpose of your explanation.)

This is insertion sort. Note that indexing starts with i = 1; the 0th position is sorted to begin. The element at a[i] is stored in `current` and the while loop shifts elements greater than `current` to the right until the place to insert `current` is established.

In the average case, this is an O(n^{2}) algorithm. On average, the number of sorted elements into which to insert is n/2. On average, half of those will be shifted before the insertion occurs. So, the average number of swaps is:

(n-1) elements * (n/2) * 1/2 = (1/4) * (n^{2} - n)

The lead term is n^{2}, so the order of growth is thus n^{2}. Again, note that the coefficient of the lead term is irrelevant in terms of determining order of growth.

**1C. (1 point)** Consider the line of code:

while (j > 0 && a[j-1] > a[j])

Why was it written this way instead of the below line of code?

while (a[j-1] > a[j] && j > 0)

Logical and works left to right. If the check to see if j == 0 is not performed before comparing elements in the array, then `a[-1]` will result in an ArrayIndexOutOfBounds exception being thrown.

TABLE 1

Elements (n) | Approximate Sort Time (ms) |

1000 | 40000 |

2000 | 160000 |

3000 | 360000 |

TABLE 2

Elements (n) | Approximate Sort Time (ms) |

1000 | 1000 |

2000 | 2200 |

4000 | 4800 |

One of these tables is the result of quick sort, the other is a result of insertion sort.

**2A. (3 points)** Which table could represent the behavior of quick sort? Which one is insertion sort? Explain using orders of growth.

The first example can be described by f(n) = .04 * n^{2}. The second can be described (roughly) as g(n) = .1 * (nlog_{2}n). Insertion sort is O(n^{2}) while quicksort is an O(nlog_{2}n). It is useful to remember that log_{2}1024 is 10 for estimation purposes.

**2B. (2 points) **A reasonable function for describing the below table is *time = 5nlogn + 4000*.

Elements (n) | Approximate Sort Time (ms) |

1000 | 54000 |

2000 | 114000 |

3000 | 184000 |

Write mathematical functions of the form *time = f(n)* for the sorts in TABLE 1 and TABLE 2.

Repeating the analysis from above, the first example can be described by f(n) = .04 * n^{2}. The second can be described (roughly) as g(n) = .1 * (nlog_{2}n). Insertion sort is O(n^{2}) while quicksort is an O(nlog_{2}n).

**3. (5 points)**

Given:

`int[] nums = {5, 3, 9, 6, 4, 2, 8, 0, 7, 1}`;

For all problems, assume that the sorts will be in *ascending* order (i.e., smallest to biggest).

A. What will `nums` look like after two passes of bubble sort?

initially:

after pass 1:

after pass 2:

The numbers in **RED** are unsorted; the numbers in **BLUE** are sorted.

Elements are compared side-by-side, left-to-right. If the left element is greater than the right element, they are swapped. Otherwise, they stay in place.

B. What will `nums` look like after two passes of selection sort?

initially:

after pass 1:

after pass 2:

The process finds the smallest unsorted element and then swaps it into place. This is selection sort. While the number of swaps required is precisely n-1, it is still an O(n^{2}) algorithm due to the number of comparisons needed to find the smallest unsorted element.

C. What would `nums` look like if, as seen in class, it were built into a maxheap to prepare a heap sort?

**BEFORE BUILDING HEAP** **AFTER HEAP BUILT**

A maxheap means that the datum at every node is larger than the data of its children. Building a maxheap works right-to-left, bottom-to-top, in this order:

- The node containing
**1**has no children and stays put. - The node containing
**7**has no children and stays put. - The node containing
**0**has no children and stays put. - The node containing
**8**has no children and stays put. - The node containing
**2**has no children and stays put. - The node containing
**4**has a child, but it has a smaller datum,**1**, so the**4**stays put. - The node containing
**6**has two children, containing**0**and**7**, at least one of which is greater than**6**. The greater of the two children is**7**, so it swaps with the**6**. The node now containing the**6**has no children, so the**6**stops there. - The node containing
**9**has two children, containing**2**and**8**, neither of which is greater than**9**, so the**9**stays put. - The node containing
**3**has two children, containing**7**and**4**, at least one of which is greater than**3**. The greater of the two children is**7**, so it swaps with the**3**. The node now containing**3**has two children, containing**0**and**6**, at least one of which is greater than**3**. The greater of the two children is**6**, so it swaps with the**3**. The node now containing the**3**has no children, so the**6**stops there. - The node containing
**5**has two children, containing**7**and**9**, at least one of which is greater than**5**. The greater of the two children is**9**, so it swaps with the**5**. The node now containing**5**has two children, containing**2**and**8**, at least one of which is greater than**5**. The greater of the two children is**8**, so it swaps with the**5**. The node now containing the**5**has no children, so the**5**stops there.

**4. (5 points) **Write mergesort in Java for `ArrayList<Comparable>` by filling in the blanks. To assist you, mergesort as fully written in Scheme is given to you. So is a substantial portion of the ArrayList abstraction. A diagram of how mergesort works is shown below.

Mergesort works as follows (from Wikipedia page on Mergesort):

- If the list is of length 0 or 1, then it is already sorted. Otherwise:
- Divide the unsorted list into two sublists of about half the size.
- Sort each sublist recursively by re-applying merge sort.
- Merge the two sublists back into one sorted list.

Here is the mergesort method. You will need to write left, right, and merge to make it work.

public static ArrayList<Comparable> mergesort(ArrayList<Comparable> alist) {

if (alist.size() < 2)

return alist;

else {

return merge(mergesort(leftHalf(alist)), mergesort(rightHalf(alist)));

}

}

**4A. (1 point)** Write `left`, which takes an `ArrayList<Comparable>` as input and returns an `ArrayList<Comparable>` that contains the first half of the input. If the number of elements in the input list is odd, then the middle element should be included in `left`.

private static ArrayList<Comparable> leftHalf(ArrayList<Comparable> alist) { ArrayList<Comparable> tmp = new ArrayList<Comparable>(); // Empty ArrayList int numElements = (int) Math.ceil(alist.size() / 2.0); // Math.ceil rounds up for (int i = 0; i < numElements; i++) { tmp.add(alist.get(i)); // the elements of the lower half of possible indices are put into tmp } return tmp; }

**4B. (1 point)** Write `right`, which takes an `ArrayList<Comparable>` as input and returns an `ArrayList<Comparable>` that contains the second half of the input. If the number of elements in the input list is odd, then the middle element should NOT be included in `right`.

private static ArrayList<Comparable> rightHalf(ArrayList<Comparable> alist) { int index = (int) Math.ceil(alist.size() / 2.0); // start copying from position index int numElements = alist.size() / 2; ArrayList<Comparable> tmp = new ArrayList<Comparable>(); for (int i = 0; i < numElements; i++) { tmp.add(alist.get(index + i)); // the elements of the upper half of possible indices are put into tmp } return tmp; }

**4C. (3 points)** Write merge which takes two `ArrayList<Comparable>`s in ascending order (as determined by Comparable) as its inputs and returns an `ArrayList<Comparable>` containing the elements of both inputs in ascending order.

private static ArrayList<Comparable> merge(ArrayList<Comparable> alist1, ArrayList<Comparable> alist2) { ArrayList<Comparable> tmp = new ArrayList<Comparable>(); while (alist1.size() > 0 && alist2.size() > 0) { // Find the smaller of the front elements in each list. Whichever that is, it gets added to tmp. // Two things of note: // * remove() in an ArrayList returns the object being removed // * This process is repeated until one of the list no longer contains elements if (alist1.get(0).compareTo(alist2.get(0)) < 0) { tmp.add(alist1.remove(0)); } else { tmp.add(alist2.remove(0)); } } // One of the two lists is empty. The while loop on the list that is empty does zero iterations. // The while loop on the list containing elements adds them to the end of tmp, completing the merging // of the two input lists. while (alist1.size() > 0) tmp.add(alist1.remove(0)); while (alist2.size() > 0) tmp.add(alist2.remove(0)); return tmp; }