delorie.com/archives/browse.cgi | search |
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/
webmaster | delorie software privacy |
Copyright © 2019 by DJ Delorie | Updated Jul 2019 |