comp.lang.idl-pvwave archive: archive » Misc. Bugs & Problems

Home » Public Forums » archive » Misc. Bugs & Problems

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

Re: Misc. Bugs & Problems [message #14519 is a reply to message #14388]

Fri, 26 February 1999 00:00

David Kastrup
Messages: 33
Registered: February 1998

Member

"Steve Scheele" <sscheele@scitor.com> writes:

> < Problem: Sort slows down considerably when sorting integer arrays
>> containing many identical values. (on NT)
>
>> Note that this seems to be platform dependent.
>
> Yes - It is also my understanding that Sort uses the sort algorithm
> that is native to the particular OS. I had thought that Sort used
> quick sort. However, quick sort slows down considerably when
> sorting arrays already in (mostly) sorted order. My testing failed
> to show this particular problem.

Only naive quicksort slows down on sorted elements. The usual variant
is the median of three quicksort picking the pivot from a median of
first, last and middle element of a range. The most inefficient
configuration for this sort is pretty hard to come up by design, but
is also O(n^2).

When you are using the GNU C library, qsort really reverts to a
mergesort method unless memory is scarce.

--
David Kastrup Phone: +49-234-700-5570
Email: dak@neuroinformatik.ruhr-uni-bochum.de Fax: +49-234-709-4209
Institut fï¿½r Neuroinformatik, Universitï¿½tsstr. 150, 44780 Bochum, Germany

Report message to a moderator

[Message index]

		Misc. Bugs & Problems By: Steve Scheele on Wed, 24 February 1999 00:00
		Re: Misc. Bugs & Problems By: steinhh on Fri, 26 February 1999 00:00
		Re: Misc. Bugs & Problems By: David Kastrup on Fri, 26 February 1999 00:00
		Re: Misc. Bugs & Problems By: Steve Scheele on Thu, 25 February 1999 00:00
		Re: Misc. Bugs & Problems By: Steve Scheele on Thu, 25 February 1999 00:00

Previous Topic:	rubberband box in an ActiveX drawwidget in VB
Next Topic:	Problem with too many open files

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Tue Dec 02 14:54:24 PST 2025

Total time taken to generate the page: 1.28368 seconds