Learn to check if a given array is already sorted for a defined sorting order i.e. ascending, descending or the custom order.
1. Overview
An array is considered sorted if every item in the array is greater or lesser than its predecessor based on the sorting order of the array.
To found such an item pair, we must iterate through all the items in the array and compare it with the next item, if it violates the sorting order then we conclude that the array is not sorted. Else, the array is sorted if there is no such item pair.
Note that the sorting order of an array can be determined in the following manners:
- All primitives are compared for their numerical values.
- Java objects that implement Comparable interface are compared based on provided logic in the overridden compareTo() method.
- All other Java objects must pass sorting order with an instance of Comparator interface.
- For reversing any comparison logic, we can always use the Comparator.reversed() instance.
2. Checking Sorted Array
2.1. Primitive Arrays
To check sorting for primitive arrays, we must check the ordering of the array items in a loop. This needs to be done in either ascending or descending order, both.
- For checking the ascending order, we are using noneMatch() API that returns true if no elements of the stream match the provided predicate. Note that API may not evaluate the predicate on all elements if it is able to find a matching pair before reaching the end of the array.
- For checking the descending order, use the allMatch() API.
int[] array = { 1, 2, 3, 4, 5 };
boolean isSorted = checkIsSortedPrimitiveArrayWithStream(array);
System.out.println(isSorted); //true
public static boolean checkIsSortedPrimitiveArrayWithStream(
final int[] array) {
if (array == null || array.length <= 1) {
return true;
}
return IntStream.range(0, array.length - 1)
.noneMatch(i -> array[i] > array[i + 1]);
}
2.2. Check Sorted Array for Comparable Objects
If the objects stored in the array implement the Comparable interface then we can use the compareTo() method to check for object equality while comparing object items for natural ordering.
Integer[] array = { 1, 2, 3, 4, 5 };
isSorted = checkIsSortedObjectArrayWithStream(ArrayUtils.toObject(array));
System.out.println(isSorted); //true
public static <T extends Comparable<? super T>>
boolean checkIsSortedObjectArrayWithStream(final T[] array) {
if (array.length <= 1) {
return true;
}
return IntStream.range(0, array.length - 1)
.noneMatch(i -> array[i].compareTo(array[i + 1]) > 0);
}
2.3. Check Sorted Array with Comparator
If the array items do not implement the Comparable interface, then for checking the sorted array we can use the Comparator instance.
User[] users = getSortedArray();
Comparator<User> firstNameSorter = Comparator.comparing(User::firstName);
isSorted = checkIsSortedObjectArrayForCustomSort(users, firstNameSorter);
System.out.println(isSorted); //true
public static <T> boolean checkIsSortedObjectArrayForCustomSort(
final T[] array, final Comparator<T> comparator) {
if (comparator == null) {
throw new IllegalArgumentException("Comparator should not be null.");
}
if (array.length <= 1) {
return true;
}
return IntStream.range(0, array.length - 1)
.noneMatch(i -> comparator.compare(array[i], array[i + 1]) > 0);
}
3. Apache Commons’s ArrayUtils
All the above methods were mainly intended to make you understand how the sorted arrays are checked. The apache common’s org.apache.commons.lang3.ArrayUtils
class contains a method isSorted()
that can do all the above comparisons in one line.
User[] users = getSortedArray();
isSorted = ArrayUtils.isSorted(array); //Natural order
System.out.println(isSorted); //true
isSorted = ArrayUtils.isSorted(array,
Comparator.comparing(User::firstName)); //Custom order
System.out.println(isSorted); //true
4. Conclusion
In this Java tutorial, we learned to check if a given array is already sorted or not. We learned to determine the sorting nature for array of primitives, array of Comparable objects and array of objects that do not implement Comparable.
It does not matter which technique we choose, the logic remains the same. So it is advisable to ArrayUtils
class from Apache Commons to avoid rewriting this simple logic.
Happy Learning !!
Comments