From: Eric Rudd Newsgroups: comp.os.msdos.djgpp Subject: Re: Library Function qsort() Exhibits N^2 Behavior Date: Wed, 29 Apr 1998 13:28:33 -0500 Organization: CyberOptics Lines: 50 Message-ID: <35477151.99373E76@cyberoptics.com> References: Reply-To: rudd AT cyberoptics DOT com NNTP-Posting-Host: rudd.cyberoptics.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Precedence: bulk Eli Zaretskii wrote: > > On Wed, 29 Apr 1998, Michel Julier wrote: > > > As far as I know it, the QSORT algorithm is "generally" fast, but in > > some special cases, that shouldn't occur often "by chance", it can > > be very slow, indeed N^2. > > AFAIK, the DJGPP version handles some of these cases by avoiding the > quadratic behavior. The DJGPP implementation of qsort uses the so-called "median-of-three" quicksort, which is one of the fastest general-purpose sort algorithms. However, there have been papers in the literature showing pathological examples where even the "median-of-three" flavor of quicksort can be O(n^2). Fortunately, the mean sort time on randomly-chosen arrays is still O(n log n). See Donald Knuth, _The Art of Computer Programming_ vol. 3, for a more extensive discussion. ANSI/ISO 9899-1990 does not specify the algorithm to be used to implement qsort, so either quicksort or heapsort could be used. In my opinion, median-of-three quicksort is generally a better choice, since it tends to be faster. If there's a situation where an untimely solution to a sorting problem could cause injury or damage to property, then heapsort is a better choice, owing to its O(n log n) worst-case behavior, but it shouldn't be imposed on everyone else, because, on the average, it will slow us down! As far as the DJGPP implementation of qsort is concerned, I am actually more worried about a problem I discovered a while ago, when I attempted to use qsort to do a sort based on floating-point values. Due to the optimizer storing one comparison value in memory, and leaving the other in the coprocessor stack to higher precision, the results of the comparison were sometimes inconsistent for equal or nearly-equal comparison values. This would have been OK, if it had only resulted in nearly-equal elements being sorted in arbitrary order, into the proper contiguous region of the array, but I found that some implementations produced an array overflow (DJGPP was among them). Since there is nothing in ANSI/ISO 9899-1990 which defines the behavior under such circumstances, this is not a bug in qsort (but rather in my comparison routine), so I didn't submit a bug report, but it is definitely a quality-of-implementation issue. I got around the problem by using volatile variables, but it still made me nervous, and I wondered if there were some way qsort could be rewritten to avoid this potential problem. -Eric Rudd rudd AT cyberoptics DOT com