Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

array
sort
recursion
iterative
communitycreator

How to check if the elements of an array are in sorted order

abhilash

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 sorted as the elements are in sorted order.
  • array - [1,4,5,4]

    • The output should be Array is not sorted as the elements are not in sorted order.

Algorithm

This problem can be solved in two ways.

  1. Recursive approach
  2. 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.

  1. Return true when the size of the array becomes zero or one.

  2. 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.

  3. 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.

Check if the array is sorted
1 of 6

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.");

    }
}
Recursive Approach

Iterative approach

The steps in the iterative approach are as follows.

  1. If the length of the array is zero or one, then the array is sorted.

  2. Start looping from the first element.

  3. 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.

  4. 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.

Check if the array is sorted
1 of 6

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.");

    }
}
Iterative Approach

RELATED TAGS

array
sort
recursion
iterative
communitycreator
RELATED COURSES

View all Courses

Keep Exploring