How to find the kth minimum element in an array

Question

I am looking for an efficient algorithm to find the k'th minimum element in an unsorted array of n elements, where 1 <= k <= n. The obvious thing is to sort the array first, then pick the k'th element, which will result in a running time of O(n * log(n)) But I guess it can be done in a more efficient way, since sorting the array seems to do "too much". For example, for k=1 the task is to find the minimum of the array, which can be done in O(n).

Does anyone know a better algorithm for k>=2?

• Wildcard: I don't know the answer offhand, but I know if you hit the CS (Computer Science) books for just a short time you'll run into the answer. For sure it's in Introduction to Algorithms, which is pretty definitive. :) But you should at least try to pick up some basic CS knowledge online so you can actually provide "what you've tried already" info like @gnat points out.
• Doc Brown: I guess this Wikipedia article is what you are looking for: en.wikipedia.org/wiki/Selection_algorithm
• NoChance: This may help:geeksforgeeks.org/kth-smallestlargest-element-unsorted-array

Answer 1

Examine the Quicksort algorithm carefully. Then consider that you want the k-largest element of the sorted array and don't care about any others, so in the Quicksort algorithm drop anything that will not affect the k-th element. In other words, don't sort any subarrays that don't contain the k-th element.

It's not optimal, but better than a complete sort.

You also might consider some tuning of the algorithm, just like Quicksort is usually tuned. What's optimal for Quicksort isn't always optimal for getting the k-th element.

Answer 2

Is the Array sorted? If yes then google for the "Median of Medians" or a "Binarysearch" or an "Interpolation-search" there are way more than these, if it is not sorted,you need to sort it first.

• user1369975: That's what I am trying to ask.Array is not sorted and so can it be done without sorting ?
• Zeljko: no, it can be done, to find the kth minimum through linear searchs. The complexity would be then O(k*n) where n is the length of the Array and k the relation of you element. Just find k-times the smalles element in the Array and that's it. if it is sorted then you can find this element VERY fast.
• user1369975: What would that algorithm be
• Zeljko: Read my answer above, i told you already 3 algorithms. There are as I said way more, but Binarysearch is easy to implement and also very fast. Interpolationsearch is not everytime that fast, it can be very bad, but with Binaryserach you can find the element you are looking for in O(log(n)). EDIT: The Median of Medians is more a strategie than a algorithm