If you make some modification to the quicksort algorithm, you will probably get the best algorithm for finding the N largest numbers of an unsorted set. Unfortunately QS is at worst O(n^2) but asymptotically O(n log n).
I would try something like:
CODE
Let L be the unsorted list, N be the number of
elements you're looking for.
QSN(List L, int N) {
if (N > 0) {
pivot = last element of L;
List HighList = the numbers in L that are larger than pivot;
List LowList = the numbers in L that are smaller than pivot;
if ((number of Elements in HighList) < N) {
output(HighList + pivot); // or store values in a List and return it when algorithm has executed
QSN(LowList, N-(number of Elements in HighList +1)); // +1 for the pivot
}
else {
QSN(HighList, N);
}
}
Sort of an divide and conquer method. Might exist better algorithms, but this is probably better than sorting first.
As mentioned in one of the comments, you could add a parameter ( QSN(List L, int N, List retList) ) to store the found elements and return the retList in the end of the algorithms execution.
Just like with QS, it's very important how to choose the pivot. If input is a list in reversed order then this algorithm is crap (O(n^2)) if pivot = last element of the list.
This post has been edited by Gloin: 23 Aug, 2008 - 08:39 AM
| 