java - Find top N elements in an Array

Question

What would be the best solution to find top N (say 10) elements in an unordered list (of say 100).

The solution which came in my head was to 1. sort it using quick sort, 2. get top 10.

But is there any better alternative?

Answer 1

The time could be reduced to linear time:

1. Use the selection algorithm, which effectively find the k-th element in a un-sorted array in linear time. You can either use a variant of quick sort or more robust algorithms.

2. Get the top k using the pivot got in step 1.