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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
