# 32.5 Exercises

Last updated

Last updated

Factual

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?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?

Conceptual

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?

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

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?Which of the following sorts are stable?

Metacognitive

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?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)?