Comment on page
32.5 Exercises
- 1.Suppose we have the array
[17, 15, 19, 32, 2, 26, 41, 17, 17], and we partition it using 3-scan partitioning using17as 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?
- 1.Which of the following arrays will result inbehavior 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
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]
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
- 1.Why does Java’s built-in
Array.sortmethod use Quicksort forint,long,char, or other primitive arrays, but Mergesort for allObjectarrays? - 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)?
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.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.
Last modified 7mo ago