Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I've come up with two ways to check to see if array is sorted and return true if it is.

public static boolean checkSortedness(int[] data)
{
    for(int i = 1; i < data.length; i++)
    {
        if(data[i-1] > data[i])
        {
            return false;
        }
    }
    return true;
}

I've also seen the i start at 0 and compare the next element instead of the previous. The other way which involves another variable is

public static boolean isSorted(int[] data)
{
     int previous = data[0];
     for(int i = 1; i < data.length; i++)
     {
         if(previous > data[i])
             return false;
         previous = data[i];
     }
     return true;
}

Which way is better and are there any alternatives?

What should the array parameter be named? I call it data but I've considered arr. This class is meant to be fairly generic.

share|improve this question
1  
Arent you missing a Point that array can be sorted in assending as well descending orders. your program only takes care about Arrays sorted in ascending order. –  Shree Jul 30 at 17:59

5 Answers 5

Three other answers, and none have picked up on the bug yet, so, here's the bug, in the second version:

The input array new int[]{4} is sorted, right? The first method will return true. The second method will return true, fine... but, what about the array new int[]{} (the empty array)? The first method will return true. The second method will throw ArrayIndexOutOfBoundsException

The two methods are not the same. The second is buggy.

To me, this makes the first method the clear winner.

Now, while you are reading this, also note that in Java, the { brace should, by convention, be at the end of a line, not on a new line. What you have in your code is C* style coding (C, C++, C#, etc.).

Also, use final when appropriate....

Your code should look like:

public static final boolean checkSortedness(final int[] data) {
    for(int i = 1; i < data.length; i++) {
        if(data[i-1] > data[i]) {
            return false;
        }
    }
    return true;
}
share|improve this answer

The better way would be your first, as you're just comparing the element A with element B and not creating a copy of the element as you are in the second version.

Additionally, to be a bit of a pedant - you don't want to name a function checkSortedness where its only returning a boolean, over isSorted where its assumed it would return a boolean.

public static boolean isSorted(int[] data){
    for(int i = 1; i < data.length; i++){
        if(data[i-1] > data[i]){
            return false;
        }
    }
    return true;
}
share|improve this answer

The name 'data' is the best given the two options, as 'arr' is just making it sound like a pirate. We already know it is an array by the type.

I prefer the first code, for all the same reasons jsanc623 said.

In case you wanted a very generic version:

public static <T extends Comparable> boolean isSorted(T[] data) {
    for (int i = 1; i < data.length; i++) {
        if (data[i - 1].compareTo(data[i]) > 0) {
            return false;
        }
    }
    return true;
}

You can use this code along with the version you have, and make other versions for the other primitive types as needed.

I've also seen the i start at 0 and compare the next element instead of the previous.

The reason why it is best to start at 1, is that it is always clear there is an element before, otherwise you have to make your terminating condition be one less - not as elegant.

Adding a Comparator version:

public static <T> boolean isSorted(T[] data, Comparator<T> comparator) {
    for (int i = 1; i < data.length; i++) {
        if (comparator.compare(data[i - 1], data[i]) > 0) {
            return false;
        }
    }
    return true;
}

Which will allow an ordering to be better controlled.

share|improve this answer
    
Good call on the type generic version –  jsanc623 Jul 30 at 17:45
1  
The generic version is ... nice, but, will not actually work for the OP's int[] array. Additionally, it would be best to take a Comparator argument. Still, I like this answer too. –  rolfl Jul 30 at 17:50
    
Added the comparator version. –  drakej Jul 30 at 18:45

Accessing an element in Java is \$O(1)\$. Both methods do \$O(n)\$ comparisons (n = number of elements). The fist one has \$O(2n)\$ accesses, the second one only \$O(n)\$, but you store a extra variable.

I would prefer the first one, cause storing costs often more time.

By the way, why don't you just sort them, using int[]?

Sorting an already sorted array often costs (depending on the implementation) also \$O(n)\$. The implementation of the standard Java array-sort is documented here.

I think if you want to sort the array if it is not sorted just use this sorting method.

References: accessing element.

share|improve this answer
    
I can't find any useful implementation details about Java array sort at the link you posted. Only that some sort implementation will be called which isn't shownin the code. –  gnasher729 Jul 30 at 22:33
    
You can't use big O analysis in such a way to analyse actual performance of the code (e.g. iterating through a linked list may be O(N) just as much as iterating through an array list but by Knuth will the performance differ in practice). As a matter of fact after the JIT has done the obvious optimizations the performance difference between the two methods will be pretty much indistinguishable - one certainly won't do twice the memory accesses. –  Voo Jul 30 at 23:41

Have you thought of doing the arithmetic comparison on every other array element, so that you can shave the number of iterations by half?

public static final boolean isAscending( final int[] data ) {
    if ( data == null || data.length < 2 ) {
        return data != null;
    }
    int secondPrevious = data[0];
    int i;
    for ( i = 2 ; i < data.length ; i += 2 ) {
        if ( data[i - 1] < secondPrevious || data[i] < data[i - 1] ) {
            return false;
        }
        secondPrevious = data[i];
    }
    // edit:
    // return i == data.length ? data[i - 1] > secondPrevious : true;
    return i != data.length || data[i - 1] > secondPrevious;
}

First, I use @Shree's advice to rename the method, so that it is known that the comparison is done in an ascending order. Second, the initial if statement takes care of a null argument or single-element array to return a result immediately. Third, at the final return statement, we take care to compare the last element with the second-last element in case that was skipped during the for-loop, else we know that we have compared all elements and can return true.

Based on my simple microbenchmarks, halving the number of iterations at the expense of two comparisons in the if statement pays off once you have more than 15 elements thereabouts...

share|improve this answer
    
This appears to be a form of loop unrolling. Are you sure its any faster? It seems like something the optimizer would do anyways if it new the values inside the array weren't going to change. –  Celeritas Jul 31 at 7:53
    
Right, it is a form of loop unrolling. I've stopped short of looking at the compiled output/the generated code though. I should do that to verify this point, thanks for the suggestion. –  h.j.k. Jul 31 at 8:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.