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/