CODEWITHSUNDEEP
algorithmsorting
new_perl
new_perl

Reputation: 7735

Algorithm to find the N~N+100 biggest elements in an array?

This is the case in limit N,100 SQL statements.

To sort the entire array is a waste when I just want to fetch the N~N+100 biggest elements.

What's the best algorithm for such situation?

Upvotes: 0

Views: 278

Answers (3)

Dennis
Dennis

Reputation: 14477

I guess that would depend on the size of the array.

For a sufficiently small array, as in selection sort, just iterate 100 times through the array, select the maximum element and remove it.

If the array is big, you could adapt the quicksort algorithm so that, in each step, it sorts either the elements bigger or smaller than the pivot, depending on if there are enough elements bigger than the pivot.

The quicksort algorithm could switch to the selection sort algorithm once the buckets become small enough.

Upvotes: 1

Luchian Grigore
Luchian Grigore

Reputation: 258618

The best you can hope for in an unsorted array is O(n) since all elements have to be checked. While traversing you simply keep the current top 100 elements in memory and if you encounter an element greater than the lowest element in the current 100, you simply remove that and add the new one. You can keep the top 100 elements in memory as a sorted queue.

Upvotes: 2

Benoit
Benoit

Reputation: 79185

Lookup an STL inplementation of std::partial_sort (C++)

Upvotes: 2

Related Questions