algorithm - finding 10 largest integers in an array in O(n) time -

let s set of n integers stored in array (not sorted). design algorithm find 10 largest integers in s (by creating separate array of length 10 storing integers). algorithm must finish in o(n) time.

i thought maybe answer using count sort , adding last 10 elements new array. apparently wrong. know better way?

method 1: can use findmax() algorithm find max number in o(n) , if use 10 time :

10 * o(n) =o(n) 

each time find max num put in new array , ignore next time use findmax();

method 2:

you can use bubble 10 times:

1) modify bubble sort run outer loop @ 10 times. 2) save last 10 elements of array obtained in step 1 new array.  10 * o(n) =o(n) 

method 3:

you can use max heap:

1) build max heap in o(n) 2) use extract max 10 times 10 maximum elements max heap 10 * o(logn)   o(n) + 10 * o(logn) = o(n)