World's most popular travel blog for travel bloggers.

# [Answers] Selection algorithm variant for an array

, ,
Problem Detail:

Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with.

Let $A = A, ..., A[n]$ be an array of $n \ge 4$ distinct keys.

Describe an efficient algorithm to find the three smallest keys in $A$. Use words.

What is the worst case number of comparisons performed by your algorithm? Try to find an exact number. Ignore floors and ceilings. Explain your answer.

I would assume you use the randomized $k$-selection algorithm where $k=3$, but if you're recursively partitioning a group of integers around a pivot I'm not sure how you'd find $k=2$ and $k=1$ short of running the algorithm 3 times.

Ideas?

Well, here's what I came up with.

You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.

Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.

But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be: $$\frac{n(n-1)}{2}$$ For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.

The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.

Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.

Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).

Hope this helps someone else.