Article View: comp.std.c
Article #1820Re: qsort(), bsearch(), and rude comparison functions
From: Felix Lee
Date: Wed, 10 Oct 1990 08:05
Date: Wed, 10 Oct 1990 08:05
11 lines
999 bytes
999 bytes
I spoke hastily. Even if comparison is random, any reasonable sorting
algorithm "makes progress" and will do no more than the worst-case
number of comparisons.
qsort() in 4.3 BSD however will have a decent chance of running past
the bounds of the array in its final insertion sort pass. Here's a
pathological comparator that guarantees this behavior:
int cmp(a, b) char * a; char * b;
{ return b - a; }
--
Felix Lee flee@cs.psu.edu
Technical Details
Message-ID:
<Fz+kg#m2@cs.psu.edu>Path:
arc1-ca.pugleaf.net!utzoo!attcan!uunet!samsung!sdd.hp.com!wuarchive!psuvax1!newsReferences:
<1990Oct6.013443.5364@twinsun.com> <1990Oct9.062455.21197@sq.sq.com> <Fex+yrm2@cs.psu.edu> <1990Oct9.231612.10881@nntp-server.caltech.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!samsung!sdd.hp.com!wuarchive!psuvax1!news From: flee@guardian.cs.psu.edu (Felix Lee) Newsgroups: comp.std.c Subject: Re: qsort(), bsearch(), and rude comparison functions Message-ID: <Fz+kg#m2@cs.psu.edu> Date: 10 Oct 90 08:05:48 GMT References: <1990Oct6.013443.5364@twinsun.com> <1990Oct9.062455.21197@sq.sq.com> <Fex+yrm2@cs.psu.edu> <1990Oct9.231612.10881@nntp-server.caltech.edu> Sender: news@cs.psu.edu (Usenet) Organization: Penn State Computer Science Lines: 11 Nntp-Posting-Host: guardian.cs.psu.edu