I correct myself, quicksort is N*log(N). -----Original Message----- From: Inger, Matthew [mailto:Inger@Synygy.com] Sent: Thursday, April 01, 2004 3:00 PM To: 'Jakarta Commons Developers List' Subject: RE: [lang] ArrayUtils.isAscending, isDescending I can't speek for collections, but as far as Arrays.binarySearch, it assumes the array is sorted. If it's not, you just don't get back the correct results you're expecting. public static int binarySearch(char[] a, char key)Searches the specified array of chars for the specified value using the binary search algorithm. The array must be sorted (as by the sort method, above) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found. 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. -----Original Message----- From: Gary Gregory [mailto:ggregory@seagullsw.com] Sent: Thursday, April 01, 2004 2:50 PM To: Jakarta Commons Developers List Subject: RE: [lang] ArrayUtils.isAscending, isDescending Hmm, I was thinking that /because/ we are talking of primitive arrays and not Object arrays, this would make things simpler in the sense that a Comparator is not needed. Does simple like isAscending(double[]) fit in [lang] and ArrayUtils as opposed to adding something to [primitives]? Or is this too much of a math-like query and should stay in math? Of course, one could argue, that starting to add isThisOrThat type of methods might open the door to other requests that might not belong. In the XP way, I would not be against adding the two is- methods for the primitive datatypes [math] needs, no more, no less. In this case we are only talking about double? I'd like to hear what others have to say. > In a few places in [math] we need to verify that double[] array > arguments > > are sorted. I did not look at the code but I am wondering: what if the array is not sorted properly? Does [math] throw an exception, sort the array and proceed? Gary > -----Original Message----- > From: Stephen Colebourne [mailto:scolebourne@btopenworld.com] > Sent: Thursday, April 01, 2004 11:25 > To: Jakarta Commons Developers List > Subject: Re: [lang] ArrayUtils.isAscending, isDescending > > Actually I would argue against. I think [lang] can supply methods to do > the > sort, but specific sort test methods doesn't feel right. > > For an Object[], having an > isSorted(Object[], Comparator) > would make sense. > > But there is no easy way to apply that kind of plugin for primitive > arrays. > Consider me -0. > > Stephen > > ----- Original Message ----- > From: "Gary Gregory" > It seems quite sensible to me. The best would be for [math] to create a > [lang] bugzilla ticket and submit a patch with unit tests. > > Thank you, > Gary > > > -----Original Message----- > > From: Phil Steitz [mailto:phil@steitz.com] > > Sent: Thursday, April 01, 2004 09:17 > > To: Jakarta Commons Developers List > > Subject: [lang] ArrayUtils.isAscending, isDescending > > > > In a few places in [math] we need to verify that double[] array > arguments > > are sorted. Would methods such as these make sense in ArrayUtils? > > Considering all ordered types and strict vs. = would lead to quite a > few > > new methods. > > > > For now, we can just code what we need in [math], but I thought I > would > > toss this out for [lang] to consider. Thoughts? > > > > Phil > > > > > > --------------------------------------------------------------------- > > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org > > For additional commands, e-mail: commons-dev-help@jakarta.apache.org > > > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org > For additional commands, e-mail: commons-dev-help@jakarta.apache.org > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org > For additional commands, e-mail: commons-dev-help@jakarta.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org For additional commands, e-mail: commons-dev-help@jakarta.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org For additional commands, e-mail: commons-dev-help@jakarta.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org For additional commands, e-mail: commons-dev-help@jakarta.apache.org