Checking if numbers in array are sorted or reverse sorted

Question

I would like to determine is an array of numbers, is always increasing (for all x, x+1 >= x) or always decreasing (for all x, x+1 =< x). If so return true. Another way to state the problem is, return true if the array is sorted or reverse sorted. Here is the code:

public static boolean isAlwaysIncreasingOrDecreasing(int[] arr) {
        //check if decreasing
        int previous = arr[0];
        boolean decreasing = true;
        for(int i = 1; i < arr.length; i++) {
            if(previous < arr[i]) {
                decreasing = false;
                break;
            }   
            previous = arr[i];
        }       

        //check if increasing
        int previous = arr[0];
        boolean increasing = true;
        for(int i = 1; i < arr.length; i++) {
            if(previous > arr[i]) {
                increasing = false;
                break;
            }   
            previous = arr[i];
        }

        //return true if always increasing or decreasing
        if(decreasing || increasing) {
            return false;
        }

        return true;
}

Any tips? Obviously duplicate values are allowed, so inputs such as 1,2,3,3,3,3....3,4,2,5,6 would be tricky.

I ask mainly out of curiosity, as the above solution would take at most 2 iterations through the array and I don't think it is possible to take less than 1, so it's not too bad :)

Answer 1

I'd write the following, seems cleaner to me. I wrote it in groovyConsole in Groovy, and adapted to Java, but I might have forgotten a semicolon or something, sorry if it doesn't compile.

public boolean isIncreasingOrDecreasing(int[] arr) {
    boolean increasing = true, decreasing = true;
    if (arr.length <= 2) {
        return true;
    }
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i-1]) {
            increasing = false;
        }
        if (arr[i] > arr[i-1]) {
            decreasing = false;
        }
        if (!increasing && !decreasing) {
            return false;
        }
    }
    return true;
}

• First, you need to define rules for empty array and array of one element (I consider them "sorted").
• Second, array of 2 elements is always "sorted".

• Third, I like the possibility to return in the middle of function/method. If you don't like it (many people do not), you may do

  if (!increasing || !decreasing) { 
     break;
  }
  

  and then

  return increasing || decreasing;
  

Answer 2

Your version is slightly misnamed. It's actually isNonincreasingOrNondecreasing. It returns true for arrays where all the entries are the same value, which is neither increasing nor decreasing.

If you don't want to duplicate the checks, you can add a bit more logic.

public static boolean isNonincreasingOrNondecreasing(int[] sequence) {
    // clear out equal entries from the beginning
    int i = 1;
    while (i < sequence.length && sequence[i - 1] == sequence[i]) {
        i++;
    }

    // if there are no entries left, then it is nonincreasing and nondecreasing
    if (i >= sequence.length) {
        return true;
    }

    int previous = sequence[i - 1];
    if (i < sequence.length && previous > sequence[i]) {
        for (; i < sequence.length; i++) {
            if (previous < sequence[i]) {
                return false;
            }

            previous = sequence[i];
        }

        return true;
    }

    for (; i < sequence.length; i++) {
        if (previous > sequence[i]) {
            return false;
        }

        previous = sequence[i];
    }

    return true;
}

This version only loops once, although it has three loops coded. It only runs one loop over any section of the array.

It also gets rid of the Boolean variables. It can return immediately since it only gets to the loops once it already knows which one to test.

Answer 3

You are traversing the array twice, it can be done in one. Since, the boolean variable once set false will remain false.

public static boolean isAlwaysIncreasingOrDecreasing(int[] sequence) {

    int previous = arr[0];
    //check if increasing
    boolean increasing = true;
    //check if decreasing
    boolean decreasing = true;
    for(int i = 1; i < arr.length; i++) {
        if(previous < arr[i]) {
            decreasing = false;
            if( !increasing ){
                break;
            } 
        } else if(previous > arr[i]) {
            increasing = false;
            if( !decreasing ){
                break;
            } 
        }
        previous = arr[i];
    }       
    //return true if always increasing or decreasing
    if( decreasing || increasing ) {
        return false;
    }
    return true;
}