How to Determine If a List Is Sorted in Java

How to determine if a List is sorted in Java?

Guava provides this functionality through its Comparators class.

boolean sorted = Comparators.isInOrder(list, comparator);

---

There's also the Ordering class, though this is mostly obsolete. An Ordering is a Comparator++. In this case, if you have a list of some type that implements Comparable, you could write:

boolean sorted = Ordering.natural().isOrdered(list);

This works for any Iterable, not just List, and you can handle nulls easily by specifying whether they should come before or after any other non-null elements:

Ordering.natural().nullsLast().isOrdered(list);

Also, since you mentioned that you'd like to be able to check for reverse order as well as normal, that would be done as:

Ordering.natural().reverse().isOrdered(list);

Determines if the array list is sorted

You have a small bug in your method. Should be :

public boolean isSorted()
{
    boolean sorted = true;        
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i-1).compareTo(list.get(i)) > 0) sorted = false;
    }

    return sorted;
}

>0 instead of !=1, you can't be sure that 1 is returned..

Java 8+ stream: Check if list is in the correct order for two fields of my object-instances

Well if you want a short-circuiting operation, I don't think an easy solution using stream-api exists... I propose a simpler one, first define a method that in a short-circuiting way will tell you if your List is sorted or not, based on some parameter:

 private static <T, R extends Comparable<? super R>> boolean isSorted(List<T> list, Function<T, R> f) {
    Comparator<T> comp = Comparator.comparing(f);
    for (int i = 0; i < list.size() - 1; ++i) {
        T left = list.get(i);
        T right = list.get(i + 1);
        if (comp.compare(left, right) >= 0) {
            return false;
        }
    }

    return true;
}

And calling it via:

 System.out.println(
          isSorted(myList, MyObj::getPercentage) && 
          isSorted(myList, MyObj::getDate));

Check if arraylist is sorted

The obvious solution:

boolean ascending = true, descending = true;
for (int i = 1; i < arr.length && (ascending || descending); i++) {
    ascending = ascending && arr[i] >= arr[i-1];
    descending = descending && arr[i] <= arr[i-1];
}

assertThat - hamcrest - check if list is sorted

[First Option]: you can write your own Matcher. Something like (disclaimer: this is just a sample code, it is not tested and may be not perfect):

@Test
  public void theArrayIsInDescendingOrder() throws Exception
  {
    List<Integer> orderedList = new ArrayList<Integer>();
    orderedList.add(10);
    orderedList.add(5);
    orderedList.add(1);
    assertThat(orderedList, isInDescendingOrdering());
  }

  private Matcher<? super List<Integer>> isInDescendingOrdering()
  {
    return new TypeSafeMatcher<List<Integer>>()
    {
      @Override
      public void describeTo (Description description)
      {
        description.appendText("describe the error has you like more");
      }

      @Override
      protected boolean matchesSafely (List<Integer> item)
      {
        for(int i = 0 ; i < item.size() -1; i++) {
          if(item.get(i) <= item.get(i+1)) return false;
        }
        return true;
      }
    };
  }

This example is with Integers but you can do it with Dates easily.

[Second option], based on the reference to contains in the OP's question: you can create a second list, ordering the original one, than using assertThat(origin, contains(ordered)). This way the eventual error is more precisely described since, if an element is not in the expected order, it will be pointed out. For example, this code

@Test
  public void testName() throws Exception
  {
    List<Integer> actual = new ArrayList<Integer>();
    actual.add(1);
    actual.add(5);
    actual.add(3);
    List<Integer> expected = new ArrayList<Integer>(actual);
    Collections.sort(expected);
    assertThat(actual, contains(expected.toArray()));
  }

will generate the description

java.lang.AssertionError: 
Expected: iterable containing [<1>, <3>, <5>]
     but: item 1: was <5>
    at org.hamcrest.MatcherAssert.assertThat(MatcherAssert.java:20)
    at org.junit.Assert.assertThat(Assert.java:865)
    at org.junit.Assert.assertThat(Assert.java:832)
    ...

How can I test whether a list is sorted with AssertJ

AssertJ offers out of the box isSorted() and isSortedAccordingTo(Comparator) for list assertions:

List<String> strings = List.of("abc", "DEF");

assertThat(strings).isSorted(); // fails as "abc" is after "DEF" lexicographically
assertThat(strings).isSortedAccordingTo(String.CASE_INSENSITIVE_ORDER); // succeeds

isSorted? Check array if is sorted in ascending or descending order in Java

Since you asked for another way to do this, here is a different approach.

What you could do is:

• Determine whether the array is (supposedly) sorted in ascending or descending order based on the first 2 elements (if these exist)
• Consider equal values when determining the supposed sorting (thanks for pointing that out @WJS)
• Then, check the rest of the array for the correct order, based on what was determined

Updated Example:

public static void main(String[] args) {
    int[] sortedAsc = { 1, 2, 3, 4, 5 };
    int[] sortedDesc = { 5, 4, 2, 1 };
    int[] unsortedArray = { 1, 8, 2, 4 };
    int[] allEqual = { 3, 3, 3, 3, 3 };
    int[] firstEqual = { 2, 2, 3, 2 };

    System.out.println(isSorted(sortedAsc));
    System.out.println(isSorted(sortedDesc));
    System.out.println(isSorted(unsortedArray));
    System.out.println(isSorted(allEqual));
    System.out.println(isSorted(firstEqual));
}

public static boolean isSorted(int[] arr) {
    boolean isAscending = false;

    if (arr.length < 2) { // if the array has less than 2 elements, must be sorted
        return true;
    }

    if (arr[0] < arr[1]) { // do we think this array is sorted ascending?
        isAscending = true;
    } else {
        int index = 0;
        while (arr[index] == arr[index + 1] && index++ < arr.length - 2) {
            // keep checking for sorting if array consists of equal values
            if (index >= arr.length - 2) {
                return true; // whole array consists of equal values
            }
        }
        // now that equal values were skipped, check for sorting again
        isAscending = arr[index] < arr[index + 1]; 
    }

    // check all elements of the array
    for (int i = 0; i < arr.length - 1; i++) {
        if (isAscending) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        } else {
            if (arr[i] < arr[i + 1]) {
                return false;
            }
        }
    }
    return true;
}

Output:

true
true
false
true
false

Sidenotes for your code:

• Instead of returning an int (0, 1), your isSorted() method should definitely return boolean.
• There is no point in the holdingArray.

---

Related Topics