Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
Computer make it possible to find information in large databases. However, the results are often too large to be returned in their entirety to the user who requests them. Computer therefore sort the results by relevance according to their own metrics. They only display the first k results on a page. The user can then go to the next page to view the next $k$ results or even go directly to the $p$-th page to view the k results for that page.
I would like such algorithm in $\Theta(n + k \log k)$
You can do a "partial" quicksort to get the n-th element in an unsorted list. For example, the algo std::nth_element exists in the C++ STL.
As an example, if you have 1000 elements and you want to sort the range from 500 to 510 then you could do:
nth_element(0, 500, 1000);
nth_element(500, 510, 1000);
quicksort(500, 510);
You can find more details about the algo there:
https://en.wikipedia.org/wiki/Selection_algorithm
