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?
- Here's an example in C++ that uses make_heap(), push_heap(), pop_heap(), sort_heap() to implement priority queue that does the same as partial_sort() in this case.jfs– jfs2011-10-30 14:17:03 +00:00Commented Oct 30, 2011 at 14:17
Add a comment |
3 Answers
Lookup an STL inplementation of std::partial_sort (C++)
1 Comment
Luchian Grigore
My bad, +1... so it's partial sort :)
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.
3 Comments
new_perl
Do you have a name for this algorithm ?
Dennis
@new_perl: This is insertion sort, dropping anything else than the
100 biggest elements.Luchian Grigore
I don't have a name but I believe this is a case where the most obvious algorithm works ok. As Dennis pointed out, the technique is similar to insertion sort.
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.
4 Comments
new_perl
How do you know the proper pivot ?
Dennis
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.
Luchian Grigore
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.
Dennis
@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.