This is the mail archive of the newlib@sources.redhat.com mailing list for the newlib project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: BUG: qsort reorders elements in already sorted array


On Wed, Jun 04, 2003 at 02:58:28PM +0200, Corinna Vinschen wrote:
> had exchanged their place.  As a figure, the order wasn't
> 
>   0 1 2 3 4 5 6 7 8 9
> 
> but
> 
>   9 1 2 3 4 5 6 7 8 0

I have a patch which works, but which perhaps slows down qsort slightly:

Index: qsort.c
===================================================================
RCS file: /cvs/src/src/newlib/libc/search/qsort.c,v
retrieving revision 1.1
diff -u -p -r1.1 qsort.c
--- qsort.c	20 Jun 2002 19:51:31 -0000	1.1
+++ qsort.c	4 Jun 2003 15:42:53 -0000
@@ -169,8 +169,9 @@ loop:	SWAPINIT(a, es);
 		}
 		pm = med3(pl, pm, pn, cmp);
 	}
-	swap(a, pm);
-	pa = pb = (char *) a + es;
+	if (cmp (a, pm) > 0)
+	  swap(a, pm);
+	pa = pb = (char *) a;
 
 	pc = pd = (char *) a + (n - 1) * es;
 	for (;;) {

First of all, qsort should swap a and pm only if they are *really* 
incorrectly ordered.

Second, it's not clear to me why in the next step the first element
is dropped from the range of entries which have to be compared.
`pa = pb = (char *) a + es;' just ignores the first element in the
following core implementation.  But the map3 stuff called before doesn't
make sure that the first element is already in order.

Btw., qsort on BSD systems has the same problem.  While newlib's code
is taken from NetBSD in 1995, it's code equivalent also to the current
implementation on OpenBSD and, as I tested by building tin 1.5.18 and my 
tiny test application, on Mac OS X.

Corinna

-- 
Corinna Vinschen
Cygwin Developer
Red Hat, Inc.
mailto:vinschen@redhat.com


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]