commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <p...@steitz.com>
Subject Re: [lang] ArrayUtils.isAscending, isDescending
Date Sat, 03 Apr 2004 03:14:39 GMT
brent@worden.org wrote:
> On Thu, 1 Apr 2004 14:59:42 -0500 , "Inger, Matthew" wrote:
> 
>>checking for something already being sorted is probably not a good
>>idea as it adds unnecessary overhead, required N - 1 comparisons
>>to verify that any given array is sorted (either ascending or
>>descending).
>>Add this on top of the O(N) comparisons required to quicksort the
>>array,
>>and you're somewhere around O(2N) comparisons before you even run the
>>algorithm expecting the sorted array.
>>
> 
> 
> However, applying a quick sort to an already sorted array adds unruly
> overhead.  In this case, quick sort degrades to a O(N^2) process. 
> Thus, IMO, it makes sense to apply the ordered check for arrays of any
> significant size.

Yes, obviously, especially if the use case is to determine whether the 
array is sorted and throw IllegalArgumentException if not ;-)

Any ideas where this should go in [math]?  The application is in testing 
that the knot points passed to SplineInterpolator.interpolate(-,-) and to 
PolynomialSplineFunction constructor form a partition.  Sorting to fix 
would be a bad idea, since you would have to parallel sort the y values or 
polynomial function arrays, resp.

Phil





---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message