It could have been an attempt at an optimization. There is a threshold with
quick sort such that below a certain number of elements, the probability is
higher that it will complete faster with an insertion sort. This threshold
is mathematically discoverable, and I once saw it derived in a probability
course. In fact, I think it was 12 (but I can't be sure)
--Charles
Bryce
McKinlay To: Mark Benvenuto <[EMAIL PROTECTED]>
<bryce@albatr cc: Classpath <[EMAIL PROTECTED]>
oss.co.nz> Subject: Re: [Fwd: java/1895: Libjava:
Arrays.sort doesn't work]
Sent by:
classpath-adm
[EMAIL PROTECTED]
02/07/2001
04:40 PM
Mark Benvenuto wrote:
> Bryce McKinlay wrote:
>
> > Here's a bug report we received through the GCC bug tracking system.
> > It looks like the qsort implementation in java.util.Arrays is broken
> > for large arrays ;-(
> >
> > Does anyone know qsort well enough to take a look?
>
> Fixed. See Patch. The bugs was a problem that depends on the fact that
our
> qsort implmentation does not happen arrays of length 7 very well. After
> recieving seven numbers from a first qsort, the qsort is suppose to
divide
> and conquer the seven numbers. The problem is since the 7 numbers are not
run
> through a proper divide (or med3) algorithm, the first number is picked
(a
> worst case qsort scenario) _incorrectly_ and the next six numbers are
> processed by ultimately an insert sort. In a proper median algorithm, if
the
> the first number was to be picked it would be the lowest one but in this
case
> it could be any value. The fix is to handle the array size = 7 by adding
an =
> sign to either the insertion sort routine or if statement wrapping the
med3
> calls. Now back to HW :(
Thanks Mark - good catch! I found a link to the code upon which the
implementation is based:
http://www.cs.dartmouth.edu/~doug/source.html
I wonder what the original intent of the code was (and why it didn't work
in our
version), since it appears that the value 7 is a special case, given the
explicit check for (n > 7) before the med3 code.
regards
[ bryce ]
_______________________________________________
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
_______________________________________________
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
