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.