Checking if an array is sorted

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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