From:	Damian Yerrick <Bullcr_pd_yerrick AT hotmail DOT comRemoveBullcr_p>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: qsort's algorithm
Organization:	Pin Eight Software http://pineight.8m.com/
Message-ID:	<fagrusc4eefie932eviurqb09ibjfo5rv2@4ax.com>
References:	<tf4qusk3quottc52jj9cmuhmqlvk48cgm7 AT 4ax DOT com> <8sjkpl$1lt$05$1 AT news DOT t-online DOT com>
X-Newsreader:	Forte Agent 1.7/32.534
MIME-Version:	1.0
Lines:	28
X-Trace:	/KHlxNN3folWtW+J+v/rQy3sIG37r4VDiQo/wDD9qkhEKGTIeoUIsZ0Cc9lvW7Dg84WeFK1IDeBA!eeRdhVidT1zyvrqEri9pJ/lvtBbNYcaueMwnPye1/zwwuTe3RjnGp5zM7hWFdIMM/8v46eMNQfOw!hdFCkw==
X-Complaints-To:	abuse AT gte DOT net
X-Abuse-Info:	Please be sure to forward a copy of ALL headers
X-Abuse-Info:	Otherwise we will be unable to process your complaint properly
NNTP-Posting-Date:	Wed, 18 Oct 2000 15:29:42 GMT
Distribution:	world
Date:	Wed, 18 Oct 2000 15:29:42 GMT
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp
Reply-To:	djgpp AT delorie DOT com

On Wed, 18 Oct 2000 09:51:31 +0200, "Peter Remmers"
<Peter DOT Remmers AT t-online DOT de> wrote:

>
>Damian Yerrick <Bullcr_pd_yerrick AT hotmail DOT comRemoveBullcr_p> schrieb...
>
>> From what I understand of the C standard, qsort() can use any decent
>> sorting algorithm.  Does DJGPP libc's qsort() have bad performance on
>> already sorted data?
>
>Is that really so? Does the standard really not determine which
>algorithm an implementaion is to use?
>I thought it'd always be the quicksort, as the name suggests.
>Again learnt something new :-)

The 'q' in qsort() is a red herring.  I haven't read the standard,
but AFAIK it only specifies O(n log n).  For example, CodeWarrior 11's
C library for Mac OS implements qsort() with Heapsort, which
_guarantees_ O(n log n) in the worst case but is on average half
as fast as average-case median of three Quicksort.

-- 
<O
( \   GNOME vs. KDE: the game!
 X    http://pineight.8m.com/nes.htm

This is McAfee VirusScan. Add these two lines to your signature to
prevent the spread of signature viruses.  http://www.mcafee.com/

- Raw text -