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 #30446 is a reply to message #30444]

Tue, 23 April 2002 12:58

Paul Van Delst[1]
Messages: 1157
Registered: April 2002

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

From Jon Bentley's "Programming Pearls", 2nd Ed, pg 119 (describing qsorts and their
efficiency):

"The qsort1 [code snippet in his book] function quickly sorts an array of random integers, but
how does it perform on nonrandom inputs? ..... consider an extreme case: an array of n
identical elements. .... the total run time is O(n^2). The run time for n=1000000 jumps from a
second to two hours."

There is also discussion of a bunch of nifty things one can do to speed up sorting. The code
snippets are only about 10-15 lines long so it would be not to difficult to translate from the
C code into IDL (I think).

Probably worth it if you or your colleague will be sorting the offending type of input data.

paulv

--
Paul van Delst Religious and cultural
CIMSS @ NOAA/NCEP purity is a fundamentalist
Ph: (301)763-8000 x7274 fantasy
Fax:(301)763-8545 V.S.Naipaul

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: Wed Oct 08 16:58:14 PDT 2025

Total time taken to generate the page: 0.00182 seconds