commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From br...@worden.org
Subject RE: [lang] ArrayUtils.isAscending, isDescending
Date Fri, 02 Apr 2004 19:48:32 GMT
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.

Brent Worden
http://www.brent.worden.org/

---------------------------------------------------------------------
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