Chapter 12: Selection Algorithm

Question 1

What will be the output if the quickselect algorithm is applied to the given array arr=[3, 1, 10, 4, 6, 5] with k given as 2?

Solution

1. Given the initial array: [3, 1, 10, 4, 6, 5], we can find the median of medians: 4 (index = 3).
2. We swap the pivot element with the first element: [4, 1, 3, 10, 6, 5].
3. We will move the pivot element to its correct position: [1, 3, 4, 10, 6, 5].
4. Now we get a split index equal to 2 but the value of k is also equal to 2, hence the value at index 2 will be our output. Hence the output will be 4.

Question 2

Can quickselect find the smallest element in an array with duplicate values?

Solution

Yes, it works. By the end of every iteration, we have all elements less than the current pivot stored to the left of the pivot. Let’s consider when all elements are the same. In this case, every iteration ends up putting a pivot element to the left of the array...