Friday, 16 August 2019

Check if an array is sorted in Java - Iterative and Recursive approach

Check if an array is sorted in Java - Iterative and Recursive approach.

Given an array, check if it is already sorted or not using both Iterative and Recursive way.

Lets see sample input and output for better understanding:
Check whether the array is sorted in Java
Check whether array is sorted or not

Algorithm

To check whether the given array is sorted in ascending order or not, we will be comparing each adjacent pairs of the array and if all the pairs are in ascending order then array is sorted else not.

  1. If the array is null or has only one element then array is already sorted.

  2. If there are more than 1 elements in the array, we will compare each adjacent elements till the end of the array and at any point if we see arr[i] > arr[i+1] we will stop and return false.  
Java Program to check if an array is sorted in Java - Iterative and Recursive
package com.javabypatel;

/*
    Check if the given array is sorted or not.
    arr[1, 2, 3]    -> True
    arr[3, 3, 3]    -> True
    arr[0, 3, -1]   -> false
    arr[4, 10, 13]  -> True
    null            -> True

 */
public class CheckIfArrayIsSorted {

    public boolean isSortedIterative(int arr[]) {
        if (arr == null) {
            return true;
        }

        boolean status = true;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i-1] > arr[i]) {
                status = false;
                break;
            }
        }
        return status;
    }

    public boolean isSortedRecursive(int arr[], int i) {
        if (arr == null || arr.length-1 ==  i) {
            return true;
        }

        if (arr[i] > arr[i+1]) {
            return false;
        }

        return isSortedRecursive(arr, i+1);
    }

    public static void main(String[] args) {
        CheckIfArrayIsSorted checkIfArrayIsSorted = new CheckIfArrayIsSorted();

        int[] arr = new int[] {1,2,3};
        System.out.println(checkIfArrayIsSorted.isSortedIterative(arr));
        System.out.println(checkIfArrayIsSorted.isSortedRecursive(arr, 0) + "\n");

        arr = new int[] {3,3,3};
        System.out.println(checkIfArrayIsSorted.isSortedIterative(arr));
        System.out.println(checkIfArrayIsSorted.isSortedRecursive(arr, 0) + "\n");

        arr = new int[] {3,3,0};
        System.out.println(checkIfArrayIsSorted.isSortedIterative(arr));
        System.out.println(checkIfArrayIsSorted.isSortedRecursive(arr, 0) + "\n");

        arr = new int[] {3,-1,0};
        System.out.println(checkIfArrayIsSorted.isSortedIterative(arr));
        System.out.println(checkIfArrayIsSorted.isSortedRecursive(arr, 0) + "\n");

        arr = null;
        System.out.println(checkIfArrayIsSorted.isSortedIterative(arr));
        System.out.println(checkIfArrayIsSorted.isSortedRecursive(arr, 0) + "\n");
    }
}
at

No comments:

Post a Comment