Find the x smallest integers in a list of length n

Question

You have a list of n integers and you want the x smallest. For example,

x_smallest([1, 2, 5, 4, 3], 3) should return [1, 2, 3].

I'll vote up unique runtimes within reason and will give the green check to the best runtime.

I'll start with O(n * x): Create an array of length x. Iterate through the list x times, each time pulling out the next smallest integer.

Edits

• You have no idea how big or small these numbers are ahead of time.
• You don't care about the final order, you just want the x smallest.
• This is already being handled in some solutions, but let's say that while you aren't guaranteed a unique list, you aren't going to get a degenerate list either such as [1, 1, 1, 1, 1] either.

Answer 1

You can find the k-th smallest element in O(n) time. This has been discussed on StackOverflow before. There are relatively simple randomized algorithms, such as QuickSelect, that run in O(n) expected time and more complicated algorithms that run in O(n) worst-case time.

Given the k-th smallest element you can make one pass over the list to find all elements less than the k-th smallest and you are done. (I assume that the result array does not need to be sorted.)

Overall run-time is O(n).