Hi,
I have a question from my homework. I think my teacher needs an algorithm like quick select for this question, is this correct?
The question:
Following a program (Subroutine) as a "black box" is given (for example, inside it is not clear and we do not even inside it) with the worst case linear time, can find the middle of n elements. Using this black box, get a simple linear algorithm that takes input i and find the element which its rank is equal to i (among the n elements)
Thanks.
This isn't really a place for homework, but you are looking for a median selection algorithm.
The question is essentially asking: given an algorithm for finding the median in O(n) time, construct an algorithm for finding the ith largest (or smallest, depending on the desired ordering) element, still in O(n) time.
In other words, suppose you an input list and are given a function median, and if you call median(list) you get the median element. You are guaranteed that median runs in O(n) time where n is the length of list. Now write a function findith which makes use of median so that you can call findith(list) and get the ith largest (or smallest) element in O(n) time.
This type of algorithm is called a selection algorithm. You can look such a thing up in your textbook for more information.