>>> 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

>> The obvious way to do it would be with a heap-based sort.  After you've
>> built the heap, you pull out the first ten elements and then stop.
>> Offhand this only seems like it'd save about half the work, though,
>> so maybe Roberto has a better idea.

> I'd like to see some elaboration.

It is, indeed, a heap-based sort, but you don't need to do so many insertions in the heap.
It works like that:


- 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). Moreover, only <N> rows (10 in this case) are kept in memory at the same time, reducing the probability to need an external-sort.

Regards

Roberto Cornacchia

===========================================================

VIRGILIO MAIL - Il tuo indirizzo E-mail gratis e per sempre
http://mail.virgilio.it/


VIRGILIO - La guida italiana a Internet
http://www.virgilio.it/

Thu, 24 Feb 2000 15:56:58 -0500
"Roberto Cornacchia" <rob.c@virgilio.it>
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 Service and other goodies at
  http://donb.photo.net.

Thu, 24 Feb 2000 13:36:54 -0800
Don Baccus <dhogaza@pacifier.com>
Re: [HACKERS] Re: about 7.0 LIMIT optimization 