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
.
array - [1,2,3,4]
Array is sorted
as the elements are in sorted order.array - [1,4,5,4]
Array is not sorted
as the elements are not in sorted order.This problem can be solved in two ways.
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 true
when 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.
O(n)
O(n)
(Considering the recursive call stack)The following slides show how the recursive approach workss.
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."); } }
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.
O(n)
O(1)
The following slides show how the iterative approach works.
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
View all Courses