Message-ID: <354702E7.2520@pobox.oleane.com>
Date: Wed, 29 Apr 1998 12:37:27 +0200
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
CC: djgpp AT delorie DOT com
Subject: Heapsort [was: Library Function qsort() Exhibits N^2 Behavior]
References: <Pine DOT SUN DOT 3 DOT 91 DOT 980429113349 DOT 1429T-100000 AT is>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Precedence: bulk

Eli Zaretskii wrote:
> 
> If somebody has a better implementation of `qsort' which is free (not
> GPL/LGPL), please point to it.  Failing that, we will need to wait until
> somebody becomes so annoyed by the current implementation that he/she
> actually sits down, corrects it, and submits the patches to DJ Delorie.
> 

For those who do not want to run the (very small) risk of one of 
these N^2 cases (when qsort() becomes very slow) happening, an 
alternative algorithm which always exhibits O(n log(n)) behaviour is 
heapsort. 

It performs more slowly than qsort on average the result of one benchmark 
(available at 
http://www.cbl.ncsu.edu/publications/1997--Talk-12-Kapur/1997--Talk-12-Kapur-HTML/node7.html)

showed that Heapsort takes on average 3,9 N log(N) comparisons per 
sorting of N elements, while qsort only takes 2,3 N log(N), which makes 
heapsort about 1,5 times slower than qsort. However, heapsort is 
guaranteed to be O(nlog(n)). 

Implementations in C of heapsort are fairly easy to find in textbooks or 
on the net. 

Francois