Check if an integer array is sorted or not

Posted by N.K. Chauhan on Mar 31, 2024

An integer array A is given, the task is to determine if A is sorted or not using recursion.

Example 1: Is {1, 2, 3, 4, 5} sorted or not.

Input: new int[]{1, 2, 3, 4, 5}
Output: true

Example 2: Is {5, 2, 3, 4} sorted or not.

Input: new int[]{5, 2, 3, 4}
Output: false


Solutions

Method 1: Recursion

An integer array A is sorted in ascending order if every A[i] < A[i+1], we can use this property to determine if the array is sorted or not using recursion.

All we need to do is, to check if A[i] < A[i+1] until the array is completely traversed, return false if condition fails and return true if entire array is traversed i.e. startIndex >= lastIndex - Base Condition.

package com.cb.recursion;

/*
 * Recursion
 * */
public class R8_CheckIfArrayIsSorted {
    public static boolean isSorted(int arr[], int start, int end) {

        // entire array is traversed
        if (start >= end)
            return true;

        // non-sorted condition is detected
        if (arr[start] > arr[start + 1])
            return false;

        // check for remaining array
        return isSorted(arr, ++start, end);
    }

    public static void main(String[] args) {
        System.out.println(isSorted(new int[]{1, 2, 3, 4, 5}, 0, 4));
        System.out.println(isSorted(new int[]{1, 2, 2, 4, 5}, 0, 4));
        System.out.println(isSorted(new int[]{1}, 0, 0));
        System.out.println(isSorted(new int[]{1, 5}, 0, 1));
        System.out.println(isSorted(new int[]{5, 1, 2, 3}, 0, 3));
    }
}

true
true
true
true
false

Complexity

The number of recursive calls depends on the size of array, hence the time complexity of this solution is O(n). We are also using "start, end" local variables, this makes the space complexity of this solution, O(n).

Related


Sum of the digits of a given number

Calculate factorial of a given number

Count ways to reach the nth stair

Print numbers from a given number to 0

Print spelling for a given number

Print numbers from 0 to a given number

Program for printing nth Fibonacci Number

Program to solve "Tower of Hanoi" problem

Calculate the Power of a Number (n^p)

Write a program to reverse a string