In-place sorting algorithm for the k smallest integers in an array on n distinct integers

Question

Is there an in-place algorithm to arrange the k smallest integers in an array of n distinct integers with 1<=k<=n?

I believe counting sort can be modified for this, but I can't seem to figure out how? Any help will be appreciated.

Answer 1

How about selection sort? It runs in place in O(n^2). Just stop after you've found k smallest elements.

Answer 2

You could use randomized selection to select the kth smallest integer in O(n) time, then partition on that element, and then use quicksort on the k smallest elements. This uses O(1) additional memory and runs in total time O(n + k log k).

Answer 3

You're looking for a selection algorithm. BFPRT will give you guaranteed worst-case O(n) performance, but it's pretty complex.

Answer 4

Do you want to partition the array so that k smallest elements are the first k elements (not necessarily sorted order)? IF so, what you are looking for is generalized median find algorithm which runs in O(n) (Just google for median find algorithm).

If you can live with randomized algorithm that finishes in linear time with high probability then all you have to do is keep picking your pivot randomly which greatly simplifies the implementation.