k-Smallest Elements in an Array in O(n)

Question

Is it possible to return the k-smallest integers in an unsorted array in time O(n), where n is the size of the array? Suppose that it doesn't matter in what order we return the answer in. Some approaches use ordered data structures like a heap to achieve this task in O(n log k) time, but I think that we can do this using a modification of Quickselect in O(n) time. Is this right?

Answer 1

Yes, this is possible. The term you’re looking for is selection algorithm, and there are several that run in time O(n), including quickselect (which technically runs in expected O(n) time).

Some of these algorithms work by rearranging the elements of the original array to position the kth smallest element at position k, all smaller elements to the left of position k, and all larger elements to the right of position k. With one of those algorithms, to find the k smallest elements, simply use the selection algorithm to put the kth-smallest element at position k and then read off the elements at positions less than k.

Other algorithms will return what the kth-smallest element is but won’t rearrange the elements. In that case, you can simply iterate over the array and output all elements less than the kth-smallest.