Checking an array is sorted in either order efficiently

Question

Here is my code, it works fine, just wondering if there any anything to make it even better.

   public static boolean isSorted(int[] arr)
   {
      int n = arr.length;
      int i = 0;
      while (arr[i] == arr[i + 1])  //  same elements at the beginning
         i++;

      if (arr[i] < arr[i + 1])      //  candidate for ascending, non-decreasing
      {
         i++;

         for (; i < n - 1; i++)
         {
            if (arr[i] > arr[i + 1])
               return false;
         }

         return true;
      }

      else                          //  candidate for descending, non-increasing
      {
         i++;

         for (; i < n - 1; i++)
         {
            if (arr[i] < arr[i + 1])
               return false;
         }

         return true;
      }
   }

It works fine, I have just avoided any class or other method.

Answer 1

Edge cases

As some comments have pointed out, your current code doesn't handle length-0 arrays, or length-1 arrays, or arrays where all elements are equal (e.g. [5, 5, 5, 5, 5]). In all of these cases, your while-loop at the very beginning of the method will hit an "array index out of bounds" exception. This needs to be fixed.

Logic flow

Conceptually, the method proceeds through the array comparing elements until one of two things happens:

1. It finds elements that are out of order. (Return false.)
2. It reaches the end of the array. (Return true.)

In this scenario, I think it helps to think of returning false as the "exceptional" case and returning true as the "default" case. Instead of having two separate return true statements, we can put one return true statement at the very bottom of the method. So if we haven't returned false earlier in the method, we will return true "by default".

Post-acceptance edit: Another simplification to the flow is possible. Your code uses a loop to pass over any duplicates at the start of the array, and then picks whether the sorting order should be ascending or descending by comparing the two elements after those leading duplicates. It is much simpler to pick the sorting order by comparing the first and last elements of the array (an idea which I borrowed/stole from sanastasiadis's answer here). This means we don't need special handling for duplicates at all.

Style

This code caught my eye:

      while (arr[i] == arr[i + 1])  //  same elements at the beginning
         i++;

Yes, if the the body is only one line, then technically you can write ifs and fors and whiles without using brackets ({ and }). And in some ways it does look cleaner. But it is also risky. If the code where you use that style gets edited later, it is very easy for someone to make a typo like this:

while (a == b)
    foo();
    bar();

...where it looks like bar() is called as part of the loop, but it's actually called after the loop. For this reason, I recommend that you get into the habit of always using brackets.

Also, I would prefer to use i + 1 < n instead of i < n - 1 for the comparisons, because we're already using i + 1 in a lot of places and I think it makes the code easier to read if we just use that more. It gives the reader one concept to grasp, instead of two. But maybe that's just me.

Putting it all together

   public static boolean isSorted(int[] arr)
   {
      int n = arr.length;

      if (n == 0 || arr[0] <= arr[n-1])   //  candidate for ascending, non-decreasing
      {
         for (int i = 0; i + 1 < n; i++)
         {
            if (arr[i] > arr[i + 1])
            {
               return false;
            }
         }
      }
      else  //  candidate for descending, non-increasing
      {
         for (int i = 0; i + 1 < n; i++)
         {
            if (arr[i] < arr[i + 1])
            {
               return false;
            }
         }
      }

      return true;
   }

Answer 2

We could make it better by making it more maintainable by simplifying the code and reducing duplication in the three for-loops. The problem is essentially checking that all successive pairs in the array are either equal or have the same sort order, so let's code it that way:

import static java.lang.Integer.compare;
import static java.lang.Integer.signum;

public static boolean isSorted(final int[] arr) {
    // The order in which the array is.
    // -1: ascending
    //  0: all elements are the same
    //  1: descending
    int arrayOrder = 0;

    for (int i = 0; i < arr.length - 1; i++) {
        // Signum is actually useless, since compare returns -1..1 but
        // we believe the documentation, not the code.
        final int pairOrder = signum(compare(arr[i], arr[i + 1]));

        if (arrayOrder == 0) {
            // All elements so far have been equal. First non-equal pair
            // defines the order expected from the following pairs..
            arrayOrder = pairOrder;
        } else if (pairOrder != arrayOrder && pairOrder != 0) {
            // If any pair is not equal and deviates from array order,
            // the array is not sorted.
            return false;
        }
    }

    return true;
}

Is this more efficient? No. There are more operations inside the for-loop, but we're talking about two equals checks between integers in an O(N) algorithm. If yours takes 4.7s on my laptop, mine takes 5.4s... for 2^31-1 elements.

A benefit in a single for-loop is that we don't need to expose the loop counter outside the loop itself. Code becomes harder to follow and more error prone when the loop counter is modified outside it's logical scope.

Answer 3

Advantages

A very good characteristic of your algorithm is that it iterates through the elements of the array only once. The next loop begins from where the previous one left the iterator i.

Disadvantages

However, as it was mentioned in the other 2 answers until now, your code does not take into consideration the case of arrays with 0 or 1 elements.

Moreover, it is not covering the case that all the elements of the array are equal (e.g. [5,5,5,5,5]).

Another disadvantage is that the loop for ascending and the loop for descending are almost duplicated, with the difference of the direction of the inequality sign.

Additionally, I would say that it's not a good practice to return from inside a loop, especially when there are more than one loops in the same method. It's preferable to declare a variable that will hold the returning value, use break/continue in the loops and then return the value of the variable, only once at the end of the method.

As a last point to highlight, when it's possible, I personally prefer using an external value that walks the values of the array rather than manipulating the iterator. In this case the iterator and the walking variable are of type int, so, the memory footprint is the same.

In a different case that the array would contain large objects, then it would be better to access random elements of the array by index, rather than copying and creating instances of that class.

Solution

For brevity and for maintainability reasons, I would choose a slightly different approach to solve this problem.

Checking if the first element is bigger than the last, we can safely assume that the array would be sorted descending (or ascending respectively).

So, in a single iteration, I wrote a loop that examines every element in the array, if it complies with the ascending or descending order that was deducted at the beginning. In order to achieve that a variable that is walking the values of the array is used edge.

public class Sorted {
    public static boolean isSorted(int[] arr) {
        boolean isSorted = true;
        // zero length and 1 length arrays can be
        // considered already sorted by default
        if (arr.length > 1) {
            // keep the first value as an edge
            int edge = arr[0];
            // if the array is sorted then it should be either ascending(true)
            // or descending(false)
            boolean ascending = arr[0] <= arr[arr.length-1];
            for (int a : arr) {
                // check if the relation between the edge and the current element
                // complies with ascending or descending
                if ((ascending == (edge < a))
                       || edge == a) {
                    edge = a;
                } else {
                    isSorted = false;
                    break;
                }
            }
        }
        return isSorted;
    }
}

In order to test the above code I wrote the below test cases:

public static void main(String[] args) {
    Assert.assertTrue(isSorted(new int[]{}));
    Assert.assertTrue(isSorted(new int[]{1}));

    Assert.assertTrue(isSorted(new int[]{0,1}));
    Assert.assertTrue(isSorted(new int[]{1,2,3,4,5}));
    Assert.assertTrue(isSorted(new int[]{2,2,3,4,5}));
    Assert.assertTrue(isSorted(new int[]{2,2,2,2,2}));

    Assert.assertTrue(isSorted(new int[]{1,0}));
    Assert.assertTrue(isSorted(new int[]{5,4,3,2,1}));
    Assert.assertTrue(isSorted(new int[]{5,4,3,2,2}));
    Assert.assertTrue(isSorted(new int[]{5,4,4,4,4}));

    Assert.assertFalse(isSorted(new int[]{1,2,3,4,1}));
    Assert.assertFalse(isSorted(new int[]{5,3,1,2,4}));
    Assert.assertFalse(isSorted(new int[]{5,4,3,2,4}));

    Assert.assertTrue(isSorted(new int[]{5,3,3,3,1}));
    Assert.assertTrue(isSorted(new int[]{5,5,3,3,1}));
    Assert.assertTrue(isSorted(new int[]{15,11,11,3,3,3,1}));
}

Additional remarks

We should always have in mind that when importing libraries to do part of the work, we should be very careful because we may introduce performance penalties.

If the library can do exactly what we want, with some configuration, then we should prefer doing it using the library, because someone has already worked to tune the implemented algorithm.