# How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2)

If we have length $$n$$ unsorted array such that each element is integer and different, how to find $$i$$ largest numbers in linear time O(n)? but $$i \leq n^{\frac{1}{2}}$$.

For example, if we have $$A = [11, 6, 8, 1, 9, 100, 88]$$ and input $$i = 2$$, then output is $$[100, 88]$$ (sorted).

Use a selection algorithm to find the $$i$$th largest number. This can be done in linear time. Then, do a second scan over the array to find all numbers larger than the $$i$$th largest number. (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $$i$$th largest and larger than the $$i$$th largest.)
• I would like to add that the classical selection algorithms (quickselect / median of medians) both partition the array so that the largest $i$ elements are also the last elements if you select on the $i$th element. – orlp Mar 27 at 6:36