Date: Sun, 22 Aug 1999 09:56:03 +0900 From: Akira Wada <a-wada@mars.dti.ne.jp> To: Archie Cobbs <archie@whistle.com> Cc: seiwald@perforce.com (Christopher Seiwald), freebsd-hackers@FreeBSD.ORG Subject: Re: anybody love qsort.c? Message-ID: <199908220056.AA00050@a.mars.dti.ne.jp> In-Reply-To: <199908210135.SAA48009@bubba.whistle.com> References: <199908210135.SAA48009@bubba.whistle.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Archie Cobbs wrote...
>Christopher Seiwald writes:
>> But as I'm proposing a change to a fairly sensitive piece of code, I'd
>> like to keep the change as modest as possible.
>
>How about this?
>
>Index: qsort.c
>===================================================================
>RCS file: /home/ncvs/src/lib/libc/stdlib/qsort.c,v
>retrieving revision 1.7
>diff -u -r1.7 qsort.c
>--- qsort.c 1997/02/22 15:03:14 1.7
>+++ qsort.c 1999/08/21 01:35:35
>@@ -153,7 +153,7 @@
> pb += es;
> pc -= es;
> }
>- if (swap_cnt == 0) { /* Switch to insertion sort */
>+ if (n <= 32 && swap_cnt == 0) { /* Switch to insertion sort */
> for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
> for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
> pl -= es)
>
>
>-Archie
>
>___________________________________________________________________________
>Archie Cobbs * Whistle Communications, Inc. * http://www.whistle.com
>
I think your modification would avoid the degeneration indicated
by Christopher Seiwald, but degrade the advantage for the dataset
sorted completely or sorted in reversed order, down to nearly
equal for random dataset.
I added a routine before selecting pivot to test current partition
sorted already and if so, to bypass partitioning. It works well
for dataset sorted in order, but doesn't work for dataset in
reversed order. I believe a reversed dataset would be partitioned
into two subpartitions sorted in order at the 1'st pass of
the partitionings. Is this incorrect ?
--------------------------------------------------------------
for qsort.c,v 1.9 1998/06/30 11:05:11
@@ -102,2 +102,5 @@
swap_cnt = 0;
+ pl = (char *)a; pn = (char *)a + (n - 1) * es;
+ while (pl < pn && cmp(pl, pl + es) <= 0) pl += es;
+ if (pl >= pn) return;
if (n < 7) {
--------------------------------------------------------------
-Akira Wada
*****************************************
和田 彬 ／ << Akira Wada >>
東京都福生市武蔵野台 1-27-5 ルネ福生 B609
(tel,fax) 042-552-1143
E-mail : a-wada@mars.dti.ne.jp
*****************************************
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?199908220056.AA00050>