How to check if the elements of an array are in sorted order
Problem statement
Given an array, check whether the elements of the array are in sorted order.
Assume that the sorted order is ascending in nature.
-
If the array is sorted, then print
Array is sorted. -
If the array is not sorted, then print
Array is not sorted.
Examples
-
array - [1,2,3,4]- The output should be
Array is sortedas the elements are in sorted order.
- The output should be
-
array - [1,4,5,4]- The output should be
Array is not sortedas the elements are not in sorted order.
- The output should be
Algorithm
This problem can be solved in two ways.
- Recursive approach
- Iterative approach
Recursive approach
The base case for this approach is when there is zero or one element left for comparison.
The steps in this approach are as follows.
-
Return
truewhen the size of the array becomes zero or one. -
Check the last two elements of the array.
a. If the last two elements are sorted, perform a recursive call with the previous element, i.e.,
n-1.b. If it returns
false, that indicates the array is not sorted. -
The recursion will eventually fall to step 1 when all the array elements are in sorted order.
- Time Complexity -
O(n) - Space Complexity -
O(n)(Considering the recursive call stack)
The recursive approach in action
The following slides show how the recursive approach workss.
Code
Example 1
import java.util.Arrays;public class Main {private static boolean isSortedArray(int[] array, int n){if(n == 1 || n == 0) return true;return array[n-2] <= array[n-1] && isSortedArray(array, n-1);}public static void main(String[] args) {int[] arr = {1,2,3,4,5};System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");System.out.println("--------");arr = new int[]{1,3,2,4,5};System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");}}
Iterative approach
The steps in the iterative approach are as follows.
-
If the length of the array is zero or one, then the array is sorted.
-
Start looping from the first element.
-
Compare every two elements.
a. If the two elements are sorted, move to the next element, i.e.,
i+1.b. Otherwise it will return
false, which indicates that the array is not sorted. -
The loop will eventually come to the end of the array when all the array elements are in sorted order.
- Time Complexity -
O(n) - Space Complexity -
O(1)
The iterative approach in action
The following slides show how the iterative approach works.
Example 2
import java.util.Arrays;public class Main {private static boolean isSortedArray(int[] array, int n){if(n == 1 || n == 0) return true;for(int i = 1; i < n; i++){if(array[i] < array[i-1] ) return false;}return true;}public static void main(String[] args) {int[] arr = {1,2,3,4,5};System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");System.out.println("--------");arr = new int[]{1,3,2,4,5};System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");}}
RELATED TAGS
CONTRIBUTOR
