0

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?

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.

-3

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.

  • That's what I am trying to ask.Array is not sorted and so can it be done without sorting ? – user1369975 Dec 24 '15 at 19:58
  • 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. – Zeljko Dec 24 '15 at 20:04
  • What would that algorithm be – user1369975 Dec 24 '15 at 20:15
  • 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 – Zeljko Dec 24 '15 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.