Selection algorithm also wud work here (O(n)).
if u know the range of numbers, u can use a bitmap(courtesy : programming pearls). Though its O(n), if the range is small, u neednot examine the full list of numbers if all the last 100 numbers are present.
On 11/10/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]
> wrote:
I consider 3 ways:
n=1 million.
1. use a 100 heap (n*log(100)?)
2. use a 1 million heap.(time O(nlogn))
3. use quicksort, each time, discard the less part. ( O(logn)?)
but I can't tell which one is the best? is there any stardard way to
do it ?
thanks!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
- [algogeeks] Re: How to select top 100 from one million numbers. Arun
