sorting - Optimal algorithm for returning top k values from an array of length N -

i have array of n floats, , wish return top k (in case n ~ 100, k ~ 10)

is there known optimal solution path problem?

could provide c algorithm?

edit: there 2 problems here: sorted , unsorted. interested in unsorted, should faster!

method 1

since k small, can use tournament method find kth largest. method described in knuth's art of programming, volume 3, page 212.

first create tournament on n-k+2 elements. knockout tennis tournament. first split pairs , compare members of pairs (as if 2 played match , 1 lost). winners, split in pairs again , on, till have winner. can view tree, winner @ top.

this takes n-k+1 compares exactly.

now winner of these n-k+2 cannot kth largest element. consider path p tournament.

of remaining k-2 pick one, , follow path p give new largest. sort of redo tournament previous winner being replaced 1 of k-2 elements. let p path of new winner. pick k-3 , follow new path , on.

at end after exhaust k-2, replace largest -infinity , largest of tournament kth largest. elements have thrown away top k-1 elements.

this takes @ n - k + (k-1) [log (n-k+2)] comparisons find top k. uses o(n) memory though.

in terms of number of compares should beat selection algorithms.

method 2

as alternative, can maintain min-heap of k elements.

first insert k elements. each element of array, if less min element of heap, throw away. otherwise, delete-min of heap , insert element array.

at end, heap contain top k elements. take o(n log k) compares.

of course, if n small, sorting array should enough. code simpler too.