32.5 Exercises

Factual

1. Suppose we have the array [17, 15, 19, 32, 2, 26, 41, 17, 17], and we partition it using 3-scan partitioning using 17 as the pivot. What array do we end up with?

2. Suppose we have the array [17, 15, 19, 32, 2, 26, 41, 17, 17], and we partition it using Tony Hoare partitioning using 17 as the pivot. What array do we end up with?

Problem 1

[15, 2, 17, 17, 17, 19, 32, 26, 41]. First we scan for the smaller elements (15, 2), then the equal elements (17, 17, 17), and finally the larger elements (19, 32, 26, 41) in the order they appear from left to right in the original array.

Problem 2

[2, 15, 17, 17, 17, 26, 41, 32, 19]. See here for a demo.

Conceptual

1. Which of the following arrays will result in $N^2$ behavior if we use quicksort which always uses the leftmost item as pivot, and which uses a stable partitioning strategy?

   • [1, 1, 1, 1, 1, 1, ..., 1]

   • [1, 2, 3, 4, 5, 6, ..., N]

   • [N, N - 1, N - 2, N - 3, ... 2, 1]

2. Repeat the exercise above, but assume that we shuffle the array before partitioning.

3. Suppose we try to use Quick Select to find the median of [17, 15, 19, 32, 2, 26, 41, 5, 9]. How many total partitioning operations will we need to complete to find the median?

4. Which of the following sorts are stable?

   • Insertion sort

   • Quicksort L3 - use leftmost item as pivot, use 3scan partitioning

   • Quicksort L3S - use leftmost item as pivot, use 3scan partitioning, shuffle before starting

   • Quicksort LTH - use leftmost item as pivot, use tony hoare partitioning

   • Quicksort PickTH - use median (computed with PICK) as pivot, use tony hoare partitioning

Problem 1

All three of these arrays are worst-case inputs for quicksort, since the size of the largest partition will only decrease by 1 each round of partitioning.

• [1, 1, 1, 1, 1, 1, ..., 1]

• [1, 2, 3, 4, 5, 6, ..., N]

• [N, N - 1, N - 2, N - 3, ... 2, 1]

Problem 2

If we shuffle, the two arrays with integers up to N are no longer guaranteed to have bad pivots since the pivot could be any item in the array with equal probability. However, the array of all 1s will still always choose a "bad" pivot, since all items in the array are equal and will end up in the left partition.

• [1, 1, 1, 1, 1, 1, ..., 1]

• [1, 2, 3, 4, 5, 6, ..., N]

• [N, N - 1, N - 2, N - 3, ... 2, 1]

Problem 3

1; after a single partitioning operation, we end up with 17 in the middle of the array. Thus, we will get 17 into this middle position and be done immediately. Note that it doesn't matter what partitioning strategy we use.

Problem 4

Insertion sort is stable, as mentioned in previous chapters.

3-scan alone is stable.

After shuffling, we cannot guarantee any ordering of items, so any partitioning strategy involving shuffling is not stable. Also, Hoare partitioning is inherently unstable, so any sort involve Hoare partiioning is also not a stable sort.

• Insertion sort

• Quicksort L3 - use leftmost item as pivot, use 3scan partitioning

• Quicksort L3S - use leftmost item as pivot, use 3scan partitioning, shuffle before starting

• Quicksort LTH - use leftmost item as pivot, use Hoare partitioning

• Quicksort PickTH - use median (computed with PICK) as pivot, use Hoare partitioning

Metacognitive

1. Why does Java’s built-in Array.sort method use Quicksort for int, long, char, or other primitive arrays, but Mergesort for all Object arrays?

2. Given that quicksort runs fastest if we can always somehow pick the median item as the pivot, why don’t we use quickselect to find the median to optimize our pivot selection (as opposed to using the leftmost item)?

Problem 1

This is because primitives don't require stability--an int is indistinguishable from any other int if they are equal by .equals(). However, this is not true for Objects, since two different Objects at different memory addresses can still be equal, and stability may be desireable when sorting objects.

Problem 2

The problem with finding the median before partioning each time is that this increases the runtime of quicksort by a significant constant factor, resulting in a much slower algorithm in practice. The very low probability of running into a worst-case quicksort means that using a time-consuming algorithm to find the median is not worth it in the majority of sorting cases.