Date: Sun, 22 Aug 1999 08:59:27 +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: <199908212359.AA00049@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 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 partitionigs. 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) pl += es; + if (pl >= pn) return; if (n < 7) { -------------------------------------------------------------- -Akira Wada 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?199908212359.AA00049>