1
$\begingroup$

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:

https://en.wikipedia.org/wiki/Quicksort

https://www.geeksforgeeks.org/quick-sort/

$\endgroup$
2
1
$\begingroup$

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

$\endgroup$
2
  • $\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 Jun 16 at 8:21
  • $\begingroup$ @CodeJack, no, it requires linear time. $\endgroup$ – D.W. Jun 16 at 8:29

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.