Selection Algorithm/Problem

Find the kth smallest item in an array $A$ of $n$ distinct numbers.

Solutions:

1. Make $k$ passes through the array, deleting the minimum number each time $\to \Theta (kn)$
2. Sort $A$, then return $A[k]\to \Theta (n\log n)$
3. Scan the array and maintain the $k$ smallest numbers seen so far in a max-heap $\to \Theta (n\log k)$
4. Create a min-heap with [Heapify]. Call deleteMin(A) $k$ times $\to \Theta (n+k\log n)$

Questions

• Which of the following options correctly represents the selection problem?
  • Given an array of size $n$ and an integer $k$, a solution to the selection problem returns the item that would be at index $k$ in the sorted array.

Related

• Quickselect
• Quick Sort
• Partition Algorithm