Is there a way to find the correct element in the array for the given index x?

Question

In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element).

Is there any algorithm to find correct element for a given index ?

Here, correct index of an element means the final index of the element which would appear after sorting the array.

Reference:

$\begingroup$ Quick select fits the bill? $\endgroup$
– Pseudonym ♦
Commented Jun 16, 2021 at 5:53 — Pseudonym, Commented Jun 16, 2021 at 5:53
$\begingroup$ en.wikipedia.org/wiki/Selection_algorithm $\endgroup$
– Yuval Filmus
Commented Jun 16, 2021 at 7:20 — Yuval Filmus, Commented Jun 16, 2021 at 7:20

D.W. · Accepted Answer · 2021-06-16 07:52:48Z

1

Yes. This is exactly what a selection algorithm does. It can be done in linear time.

answered Jun 16, 2021 at 7:52

D.W.♦

166k21 gold badges230 silver badges490 bronze badges

$\begingroup$ For a single index, can it be done in logarithmic time? For example, if we want to find the correct element at ith index, can it be found in logarithmic time ? $\endgroup$
– CodeJack
Commented Jun 16, 2021 at 8:21
$\begingroup$ @CodeJack, no, it requires linear time. $\endgroup$
– D.W. ♦
Commented Jun 16, 2021 at 8:29

Add a comment |

1 Answer 1