Re: [Fwd: java/1895: Libjava: Arrays.sort doesn't work]

[cowboyd]

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 
<address@hidden>                               
                    <address@hidden        cc:     Classpath <address@hidden>   
                                  
                    oss.co.nz>           Subject:     Re: [Fwd: java/1895: 
Libjava: Arrays.sort doesn't work]      
                    Sent by:                                                    
                                   
                    classpath-adm                                               
                                   
                    address@hidden                                              
                                       
                                                                                
                                   
                                                                                
                                   
                    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
address@hidden
http://mail.gnu.org/mailman/listinfo/classpath