Home > Enterprise >  Check if array is sorted using recursion
Check if array is sorted using recursion

Time:05-01

I am getting true as answer even for unsorted(isNonDescending) arrays. Where is the bug? I want to break the array into smaller problem from the start of the array only.

//Check for isNonDescending.

public class AlgoAndDsClass {

    public static void main(String args[]) {

        int[] unsortedArry = { 1, 2, 3, 4 };
        int[] unsortedArry2 = { 1, 2, 4, 3 };
        System.out.println(isSorted(unsortedArry, unsortedArry.length));
       System.out.println(isSorted(unsortedArry2, unsortedArry2.length));


    }

    private static boolean isSorted(int[] arr, int size) {
        if (size == 0 || size == 1)
            return true;

        if (arr[0] > arr[1]) {
            return false;
        }
        System.out.println(arr.length);
        boolean smallwork = isSorted(arr, size - 1);

        return smallwork;

    }

CodePudding user response:

Instead of passing the size of the array as a parameter, which makes no sense anyway, because you can simply call arr.length, you should pass a starting index and increase it with each recursive call until you have reached the length of your array.

private static boolean isSorted(int[] arr, int index) {
    if(arr.length == 0 || arr.length == 1 || index == arr.length - 1){
        return true;
    }
    if (arr[index] > arr[index   1]) {
        return false;
    }
    return isSorted(arr, index   1);
}

and call from main with 0 as a starting index

System.out.println(isSorted(unsortedArry,0));
System.out.println(isSorted(unsortedArry2,0));

CodePudding user response:

you keep on checking the same 2 elements, try using the size variable instead as the arrray indexes. For exmaple, if the first 2 elements are sorted you'll get true, thats because you check only the first two elements in the arrray.

CodePudding user response:

Array is sorted if the sub-array from the start and up to one element before last is sorted and the last element is larger or equal to the element before last one.

  • Related