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
Does anyone know a better algorithm for k>=2?