Re: [HACKERS] Re: about 7.0 LIMIT optimization

At 03:56 PM 2/24/00 -0500, Roberto Cornacchia wrote:
>>>> QuickSort: 1.6E+14
>>>> SortStop: 1.5E+11
>>
>>> Are there some zeroes missing here?  That sounds like an awful lot of
>>> operations for a quicksort of only 1E5 elements...
>
>> Yeah, obviously one or more of his numbers are wrong.  Let's see, a
>> [...]
>
>Yes I'm sorry, those numbers were completely wrong, I shoud have realized
immediately. Here are the correct ones:
>
>QuickSort: 1.66096e+06
>SortStop:  1.00327e+05

Yeah, there you go!  Thanks...

>- put first 10 rows in the heap, whith the worst value on head
>- compare each other 99990 rows with the current head
>- if new row is better, then 
>    trash current head and insert new row into the heap,
>  otherwise trash the new row.
>
>In this way the number of insertions in the heap is considerably lower
(you can find more details on Knuth, vol III).

"Sorting and searching", right, where would we be without Knuth?


- Don Baccus, Portland OR <dhogaza@pacifier.com> Nature photos, on-line guides, Pacific Northwest Rare Bird Alert
Serviceand other goodies at http://donb.photo.net.