From: not_valid@nospicedham.comcast.net
> "Terje Mathisen" wrote in message news:okns64$1g16$1@gioia.aioe.org...
> Robert Wessel wrote:
> > On Wed, 19 Jul 2017 13:03:43 +0000, Robert Prins
> > wrote:
> >> For what it's worth, I do have working Shellsort and Heapsort
> >> routines, so I'm not really looking for code.
> > If I understand your problem correctly, you want to extract the top
> > N elements of a list. While sorting the whole list is obviously one
> > way of doing this, this is a selection problem, not a sorting
> > problem, and can be done rather faster than sorting the whole list.
> Exactly right.
> The largest set (40) is still such a tiny value that it is really
> trivial to just maintain a running top list of the top 40 entries:
> Each time you get a new entry you compare it with the last and discard
> immediately if below, otherwise I'd just replace #40 with the current
> entry and then do a single iteration bubble sort to move it to the
> correct spot.
> You can of course use binary search to reduce this to max 6 compares,
> followed by a block copy to shift the bottom part down to make roon in
> the right spot.
> This key is that 40 is such a small number that on average you will need
> very few comparisons for the naive code.
I consider it unfortunate that you snipped Robert Wessel's advice to
implement the top 40 list as a priority queue via a heap since the O.P.
stated above that he already has working heapsort code, so it should
be a breeze to implement a heap (or actually running 3 heaps at the
same time in the context of this problem so as to only read each data
item once).
I know you know this, but am not sure why you didn't comment on the
possibility.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
