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
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
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/