The problem is I have a list of 1 million numbers, but I only want the 10 first of the sorted list, but I do not want to sort the whole list? Is that possible?
views:
77answers:
2
+4
A:
Yes. You just run through the list once, and store the ten smallest numbers. The algorithm will be O(n) (actually, O(n*10) worstcase)
Foreach (list)
- Check if current item is smaller than the biggest item in the sorted Array[10]
- If so, put the current item at the right spot (sorted) in the array (insertionsort), bumping away the biggest item.
Konerak
2010-06-28 19:42:58
You could turn that 10 into a lg based constant by using a heap for your "list" of 10. :-)
glowcoder
2010-06-28 19:46:09
O(n*10) = O(n).
recursive
2010-06-28 20:11:42
recursive: offcourse, but this makes it clear that when the number 10 gets higher (say, you want half the list sorted), the O will change, and a simple array won't do. You'll then need a better datastructure like glowcoder said.
Konerak
2010-06-28 20:17:31
+3
A:
What you want is a Priority Queue. Insert each number into a priority queue. If the size of the queue exceeds 10, then remove the smallest (or largest) value. The values that remain in the queue at the end are the 10 largest (or smallest).
If the queue is implemented using a Heap, then this can be a very effecient algorithm.
Jeffrey L Whitledge
2010-06-28 19:43:02