comp.lang.idl-pvwave archive: archive » Re: Bizarre slowness from sort()

Home » Public Forums » archive » Re: Bizarre slowness from sort()

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Re: Bizarre slowness from sort() [message #30443 is a reply to message #30440]

Tue, 23 April 2002 14:11

William Clodius
Messages: 30
Registered: December 1996

Member

Jonathan Joseph wrote:

> I had the following enlightening discussion about qsort with a
> programmer from RSI who responded to my post, but I'm still not
> entirely convinced. Can anyone comment on this?
>
> -Jonathan
>
> (posted with permission)<snip>

They should not be using quicksort in any form for integer or floating
point data. The quoted average 0(n ln(n)) performance is not as good as the
0(n) that is achievable for these special data types. (Further this
"average" has assumptions about the randomness of data that is often not
obeyed in practice.) For other datatypes, e.g., strings, they should also
not be using quicksort, as other sorting algorithms have the same 0(n
ln(n)) asymptotic behavior and their relative scale factors depend on the
relative costs of memory fetching, storing, and comparisons. Typical
arguments favoring quicksort are based on values for these relative costs
that were typical for integer and floating point data on machines of the
late 70's/early 80's. See Richard O'Keefe's discussion of his applicative
merge sort in a variety of newsgroups in the 90's.

Report message to a moderator

[Message index]

		Re: Bizarre slowness from sort() By: thompson on Tue, 23 April 2002 15:42
		Re: Bizarre slowness from sort() By: William Clodius on Tue, 23 April 2002 14:11
		Re: Bizarre slowness from sort() By: Robert Stockwell on Tue, 23 April 2002 14:10
		Re: Bizarre slowness from sort() By: Paul Van Delst[1] on Tue, 23 April 2002 12:58
		Re: Bizarre slowness from sort() By: Jonathan Joseph on Tue, 23 April 2002 11:56
		Re: Bizarre slowness from sort() By: Ivan Valtchanov on Tue, 23 April 2002 08:58
		Re: Bizarre slowness from sort() By: Jonathan Joseph on Tue, 23 April 2002 09:14

Previous Topic:	24-bit color problem on Red Hat Linux 7.1
Next Topic:	ENVI Convert Arcview registration problems

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Fri Oct 10 01:44:24 PDT 2025

Total time taken to generate the page: 0.55846 seconds