Check if an array is sorted, return true or false

Question

I am writing an easy program the just returns true if an array is sorted else false and I keep getting an exception in eclipse and I just can't figure out why. I was wondering if someone could take a look at my code and kind of explain why I'm getting an array out of bounds exception.

public static boolean isSorted(int[] a) 
{
    int i;
    for(i = 0; i < a.length; i ++);{
        if (a[i] < a[i+1]) {
            return true;
        } else {
            return false;   
        }
    }
}
public static void main(String[] args)
{
    int ar[] = {3,5,6,7};
    System.out.println(isSorted(ar));   
}

Solution 1

Let's look at a cleaner version of the loop you constructed:

for (i = 0; i < a.length; i++); { 
    if (a[i] < a[i + 1]) {
        return true;
    }
    else {
        return false;
    }
}

I should first point out the syntax error in the original loop. Namely, there is a semicolon (;) before the curly brace ({) that starts the body of the loop. That semicolon should be removed. Also note that I reformatted the white-space of the code to make it more readable.

Now let's discuss what happens inside your loop. The loop iterator i starts at 0 and ends at a.length - 1. Since i functions as an index of your array, it makes sense pointing out that a[0] is the first element and a[a.length - 1] the last element of your array. However, in the body of your loop you have written an index of i + 1 as well. This means that if i is equal to a.length - 1, your index is equal to a.length which is outside of the bounds of the array.

The function isSorted also has considerable problems as it returns true the first time a[i] < a[i+1] and false the first time it isn't; ergo it does not actually check if the array is sorted at all! Rather, it only checks if the first two entries are sorted.

A function with similar logic but which checks if the array really is sorted is

public static boolean isSorted(int[] a) {
// Our strategy will be to compare every element to its successor.
// The array is considered unsorted
// if a successor has a greater value than its predecessor.
// If we reach the end of the loop without finding that the array is unsorted,
// then it must be sorted instead.

// Note that we are always comparing an element to its successor.
// Because of this, we can end the loop after comparing 
// the second-last element to the last one.
// This means the loop iterator will end as an index of the second-last
// element of the array instead of the last one.
    for (int i = 0; i < a.length - 1; i++) {
        if (a[i] > a[i + 1]) {
            return false; // It is proven that the array is not sorted.
        }
    }

    return true; // If this part has been reached, the array must be sorted.
}

Solution 2

For anyone using Java 8 and above, here's a simple one-liner:

public static boolean isSorted(int[] array) {
    return IntStream.range(0, array.length - 1).noneMatch(i -> array[i] > array[i + 1]);
}

Or a logically-equivalent alternative:

public static boolean isSorted(int[] array) {
    return IntStream.range(0, array.length - 1).allMatch(i -> array[i] <= array[i + 1]);
}

Solution 3

With this expression, a[i+1], you are running off the end of the array.

If you must compare to the next element, then stop your iteration 1 element early (and eliminate the semicolon, which Java would interpret as your for loop body):

// stop one loop early ---v       v--- Remove semicolon here
for(i = 0; i < a.length - 1; i ++){

Solution 4

int i;
for(i = 0; i < a.length - 1 && a[i] < a[i+1]; i++){}
return (i == a.length - 1);

• only accesses array elements, last part of end condition are not processed if first part ist false
• stops on first not sorted element

Solution 5

a[i+1] when i == a.length will give you that error.

For example, in an array of length 10, you have elements 0 to 9.

a[i+1] when i is 9, will show a[10], which is out of bounds.

To fix:

for(i=0; i < a.length-1;i++)

Also, your code does not check through the whole array, as soon as return is called, the checking-loop is terminated. You are simply checking the first value, and only the first value.

AND, you have a semi-colon after your for loop declaration, which is also causing issues

View more solutions

Comments

[Richard Tingle]

an int array cannot be null. Also while your code solves the exception it doesn't actually achieve what the method sets out to achieve

[user2101463]

Ahhhh! I see now, Thank you for your help

[Jeff Voss]

noticed this was a question about java, but reviewing the src of .every() will shed some light ;)

[Dan M.]

This answer is wrong not only because it's for js, but also because it doesn't do what it's supposed to do. every function tests only one element at the time, so arg b in this case is the index of element a. So the provided function only tests if arr[i] > i. For [5, 3, 5] it returns true, while for [0, 1, 2] it returns false.

[B001ᛦ]

Would you explain your answer please?

[Toby Speight]

Welcome to Stack Overflow! While this code snippet may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post. Remember that you are answering the question for readers in the future, not just the person asking now! Please edit your answer to add explanation, and give an indication of what limitations and assumptions apply.

[JimHawkins]

Welcome to stack overflow :-) Please look at How to Answer. You should provide some information why your code solves the problem. Code-only answers aren't useful for the community.

[Nader Ghanbari]

Worst case complexity is O(n). What is the average time complexity given that data are randomly chosen from a normal distribution? Is it really O(1)? Seems like a bunch of diminishing geometric series whose sum is another geometric series which just gives 4 as n approaches n → ∞ hence O(1). Is this true?

[Richard Tingle]

@nader feels plausible, at each data point the change of early outing is 0.5 so the average time complexity must be much less than O(n)

[Moshiour]

first one logic is not right.. new int[]{1, 2, 4, 5, 6, 1} it fails for the last element.

[Jacob G.]

@Moshiour Thanks a lot for pointing that out. anyMatch should have been noneMatch.

[Moshiour]

Welcome mate :)

[jpenna]

You should provide some explanation about the code, so people don't have to decode it. For example, what is i? Where did you declare it? You are validating an ascendent or descendent sort? Try not to answer with just code. Check the How to Answer for more details.

[con]

a verbal explanation is often helpful

[Tushar Nikam]

we simple check the neighbour element that is (a[i] > a[i-1] ) and return accordingly

[gillall]

The condition ( a[i] > a[i+1] ) is always false in a sorted array. From any sorted array pick any position and swap with any other and the condition will be true exactly where that you put/removed the item.

[E-A]

(a[i] > a[i + 1] || a[i] == a[i + 1]) would be better

[Richard Tingle]

@E-A really? If 2 items are equal that is fine since a sorted list could indeed have equal values next to each other

[E-A]

In my case, there were inputs like [1,1,2,3,4,4]

[Richard Tingle]

@E-A And that's a sorted array right. So should return true right?