0

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?

new_perl
  • 7,345
  • 11
  • 42
  • 72
  • Here's an [example in C++ that uses make_heap(), push_heap(), pop_heap(), sort_heap()](http://stackoverflow.com/questions/2486093/millions-of-3d-points-how-to-find-the-10-of-them-closest-to-a-given-point/2486341#2486341) to implement priority queue that does the same as partial_sort() in this case. – jfs Oct 30 '11 at 14:17

3 Answers3

2

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

Benoit
  • 76,634
  • 23
  • 210
  • 236
2

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.

Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
1

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.

Dennis
  • 14,264
  • 2
  • 48
  • 57
  • How do you know the proper pivot ? – new_perl Oct 30 '11 at 12:56
  • To avoid worst-case scenarios, pivots usually get selected either at random or as median of the first, last and middle element of the bucket. – Dennis Oct 30 '11 at 13:00
  • Even for small arrays (I'm assuming here more than 100 elements), I don't see the point of traversing the array 100 times, when you can do it in 1 pass. – Luchian Grigore Oct 30 '11 at 13:03
  • @LuchianGrigore: You are right. Your method is better than my method for small arrays. +1 for it. Still, large arrays should be narrowed down using adapted quicksort. – Dennis Oct 30 '11 at 13:23