Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 19 Aug 1999 12:14:46 -0700 (PDT)
From:      Christopher Seiwald <seiwald@perforce.com>
To:        archie@whistle.com, gurney_j@efn.org, narvi@haldjas.folklore.ee
Cc:        freebsd-hackers@freebsd.org
Subject:   Re: anybody love qsort.c?
Message-ID:  <199908191914.MAA10750@perforce.com>
In-Reply-To: <199908191810.LAA94818@bubba.whistle.com>

next in thread | previous in thread | raw e-mail | index | archive | help
Answers to sundry comments:

| why don't you implement this w/ the 5 element median selection qsort
| algorithm?  my professor for cis413 talked about this algorithm and
| that it really is the fastest qsort algorithm...   

qsort algorithms are like stock market tips: only good in retrospect.
The bentley scheme uses a 9 element median selection (80% better?).

| Doesn't the qsort just switch to isort *if* the partition to sort is short
| enough? 

Yes -- if it is < 7 elements, it always does isort.  But the problem is
that it will switch to isort if it believes the data is mostly sorted, and
it comes to this conclusion incorrectly.  Unfortunately, I haven't found
a sure-fire way to improve this.

| The code is complex but from a quick glance it appears that the decision
| to switch to insertion sort does not depend on the total array length.

Right.  Actually, once you get into it, the code is relatively simple.
It is one of the features of the Bentley code.

Christopher


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message




Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199908191914.MAA10750>