0

I am looking for an algorithm that returns the indice of the kth largest element in a array. I found many algoritms but most of them return the list of the k largest elements (Extract K largest elements from array of N integers in O(N + K) time, Best way to retrieve K largest elements from large unsorted arrays?, ...).
In this case, only the indice of the kth largest element is needed. All the kth largest elementS are not needed. As array and k are large, I would like to avoid the allocation of an array (or other structure, e.g. linked list) of dimension k and the initial array must be unchanged. What is (are) the most efficient algorithm(s) ?

Stef1611
  • 1,978
  • 2
  • 11
  • 30
  • You could take a look at [quickselect](https://en.wikipedia.org/wiki/Quickselect), an algorithm inspired by quicksort which doesn't sort the array but finds the kth element. It doesn't allocate a new array, but it does move a few elements around in the old array. – Stef Sep 09 '22 at 08:52
  • @Stef. The initial array must be unchanged – Stef1611 Sep 09 '22 at 09:01
  • Does this answer your question? [How to find the Kth smallest integer in an unsorted read only array?](https://stackoverflow.com/questions/30728297/how-to-find-the-kth-smallest-integer-in-an-unsorted-read-only-array) – Stef Sep 09 '22 at 09:25

1 Answers1

1

Finding the k'th largest element in an array cannot be done in less than O(k*n) (or O((n-k)*n)) time without modifying the input array or allocating more than O(1) additional space. If you do not permute the array, you can't do any better than brute force; if you do permute the array, you can't reverse the permutation without keeping extra information around to do it.

(A randomized selection algorithm can achieve linearithmic expected time, but cannot improve on the worst-case time.)

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • 1
    Hi! Great answer, but could you please add some justification for your claims? Unfortunately it happens relatively often that people post answers claiming something isn't possible, just because they don't know how to do it, when in fact it is. It would be great if you could add some reference or justification to make it clear that this isn't one of those answers. – Stef Sep 09 '22 at 09:18
  • @Sneftel. Thanks for answer. Would one solution be to keep a trace of permutations to reverse them after ? But, if there is too much permutations, it is best to store the k elements, ... I though that this problem would be simple. I have written a "naive code" and I though I could to better easily. (Find the smallest element (s) in array[1,K], Get next element : i, If A[i]>s get smallest in array[1,i]) – Stef1611 Sep 09 '22 at 09:21
  • 1
    @Stef1611 You can definitely reverse the permutation, but storing the information to do that requires an extra allocation. – Sneftel Sep 09 '22 at 09:22
  • @Stef. In a few word. I would like to have only the kth largest element because after I randomly choose L ( – Stef1611 Sep 09 '22 at 09:27
  • 2
    @Stef1611 It's a lot easier and faster to *compare* a value to the k'th largest value, than it is to *find* the k'th largest value. If that's what you're actually trying to do, it sounds like you have the [XY problem](https://xyproblem.info/). – Sneftel Sep 09 '22 at 09:28
  • @Sneftel. I agree. This my problem : storing permutations or storing k elements ? – Stef1611 Sep 09 '22 at 09:29
  • @Sneftel. I your comment, how can I compare a value to the kth largest value if I have not this value ? And to have it, I have to find it. Something wrong ? – Stef1611 Sep 09 '22 at 09:32
  • 1
    @Stef1611 Compare your target value to each value in the array and count how many are bigger. See if that count is more or less than k. – Sneftel Sep 09 '22 at 09:33
  • 1
    @Stef1611 You have a value x and want to estimate whether rank(x) is more or less than k. That doesn't require finding the element which is ranked k. – Stef Sep 09 '22 at 09:34
  • 1
    @Stef1611 Note that if L is large, it might be best to find the kth element first, as a preprocessing step, rather than estimate the ranks of L elements. – Stef Sep 09 '22 at 09:35
  • Thanks to you (Sneftel and Stef). Counting and changing k is the clue because I have an idea of my distribution. In reality, what I need is to separate my datas in two groups. – Stef1611 Sep 09 '22 at 09:37