Date: Wed, 29 Apr 1998 10:45:00 +0300 (IDT) From: Eli Zaretskii To: Kbwms cc: djgpp AT delorie DOT com Subject: Re: Library Function qsort() Exhibits N^2 Behavior In-Reply-To: <3d7646f9.3545ff42@aol.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Precedence: bulk On Tue, 28 Apr 1998, Kbwms wrote: > The standard library utility qsort() exhibits the dreaded quadratic > behavior on some sort targets. Some years ago, I wrote a program > that tests sort functions. The program was described in an article > that was published in an issue of C/C++ Users Journal. Here is what > my test says when qsort() is run on various kinds of targets, each > 20,000 in size: Thanks, this is all very educational. However, I'm puzzled what is it exactly that you are trying to say here? Are you telling that the DJGPP's version of `qsort' is intolerably slow in some cases? Then let's see comparison to more than a single other implementation, and let's discuss how `qsort' can be made faster in these cases. Do you have a patch to suggest that will make `qsort' it faster? If so, please post that patch. Do you have an alternative version of `qsort' whose source is freely available and which you suggest to include in the next release of DJGPP? If so, either post that source or point us to where it can be obtained. If your only intent was to post results of testing a function, IMHO some results from other implementations (more that a single unnamed alternative) should also be published, to put the measured data in some perspective. Publishing results with no clear summary (like ``this is too slow, and here's the evidence'') tends to confuse newcomers who don't have any prior knowledge of the subject matter. You already had such a case after your previous posting about testing `rand'. FYI, the version of `qsort' in the DJGPP library uses a slightly modified algortithm for picking up the first element, which is better in some pathological cases. See the library sources for more details.