Tags: quickselect
True or False: quickselect requires the input array to be sorted in order to function correctly.
False.
quickselect works on unsorted arrays: it partitions the array around a pivot, which puts the pivot in its correct sorted position, and then recurses only on the side that contains the \(k\)th smallest element. If the array were already sorted, we wouldn't need quickselect at all; we could just look up the element at index \(k\) in \(\Theta(1)\) time.
Tags: quickselect
True or False: in order to guarantee that its output is correct, quickselect must be called on a sorted list.
False.
quickselect works on unsorted arrays: it partitions the array around a pivot, which puts the pivot in its correct sorted position, and then recurses only on the side that contains the \(k\)th smallest element. If the array were already sorted, we wouldn't need quickselect at all; we could just look up the element at index \(k\) in \(\Theta(1)\) time.
Tags: loop invariants, quickselect
Recall the partition operation from quickselect. Which of the following arrays could have been partitioned at least once? Select all that apply.
The second, third, and last all should be selected.
Tags: quickselect
Which of the following arrays could have been partitioned at least once? (Select all that apply)
Hint: there are three.
[15, 25, 35, 45, 55], [6, 5, 1, 8, 3, 15], and [0, 10, 15, 18, 20, 30, 29, 19]. After a partition, the pivot is in its final sorted position: everything to its left is smaller and everything to its right is at least as large. So an array could have been partitioned only if some element has this property. In [15, 25, 35, 45, 55] every element does; in [6, 5, 1, 8, 3, 15] the 15 does; and in [0, 10, 15, 18, 20, 30, 29, 19] the 0 (and the 10, 15, and 18) does. None of the other arrays has such an element.
Tags: quickselect
The code for quickselect is shown below. It is the same as the code provided in lecture, except that it contains an added print statement.
import random
def quickselect(arr, k, start, stop):
"""Finds kth order statistic in numbers[start:stop])"""
print("hello world!") # <--- here is the print
pivot_ix = random.randrange(start, stop)
pivot_ix = partition(arr, start, stop, pivot_ix)
pivot_order = pivot_ix + 1
if pivot_order == k:
return arr[pivot_ix]
elif pivot_order < k:
return quickselect(arr, k, pivot_ix + 1, stop)
else:
return quickselect(arr, k, start, pivot_ix)
Suppose quickselect(arr, 3, 0, 10) is called with arr = [5, 2, 8, 3, 1, 6, 9, 7, 4, 0].
What is the fewest number of times that ``hello world!'' can possibly be printed? Your answer should be a number, and not in terms of \(n\).
1
What is the greatest number of times that ``hello world'' can possibly be printed? Your answer should be a number, and not in terms of \(n\).
10
Tags: quickselect
Suppose a quickselect is being performed on an array. In the middle of the quickselect, you are told that the array has been partitioned exactly twice thus far, and that the third order and sixth order statistics have been identified as a result. Which one of the following arrays is partitioned in this manner?
[10, 5, 20, 45, 21, 52, 67, 54]. The two pivots must be the 3rd and 6th smallest elements, so they must sit at indices 2 and 5 with everything to their left smaller and everything to their right larger. In this array, 20 (index 2) and 52 (index 5) both satisfy this. In the first array, 4 has 6 to its left; in the third, 2 has 3 to its left; and in the fourth, 14 at index 5 has 45 to its left.
Tags: quickselect
Suppose quickselect is used on an array of size 11 to find the median. The median is located as the second element of the array (at index 1), but the rest of the array is sorted in descending order. If we change the behavior of quickselect so that the pivot index is no longer random, instead always choosing start as the pivot index (pivot_ix = start), how many calls to quickselect will need to be made to find the median? Assume that quickselect is using the in_place_partition algorithm from lecture. You may also assume that for the first call of quickselect start = 0 and stop = len(arr).
Answer: 3. For example, take arr = [10, 5, 9, 8, 7, 6, 4, 3, 2, 1, 0], whose median is 5. The first call uses 10 (the maximum) as the pivot; in_place_partition moves it to the end, giving [0, 5, 9, 8, 7, 6, 4, 3, 2, 1, 10], so we recurse on indices 0 through 9. The second call uses 0 (the minimum) as the pivot, which stays at index 0, so we recurse on indices 1 through 9. The third call uses the median, 5, as the pivot, and after partitioning it lands at index 5, so it is returned.