Check if an array is sorted or not using recursion-CodePudding

Here is my code:

def isSorted(arr):
    n = len(arr)
    if n == 0 or n == 1:
        return True
    elif arr[n-2] > arr[n-1]:
        return False
    return isSorted(arr[0:n-1])

arr = [1,9,9,4,5]    
isSorted(arr)    
if isSorted:
    print("yes")
else:
    print("no")

Answer is always yes, even if the array is unsorted. Can anybody please explain what mistake am I making?

CodePudding user response：

Your code was fine with the exception of the error noted in the comments: you were ignoring the return value of isSorted(arr) by just checking if isSorted:. isSorted is a callable (and not None or zero or an empty string, etc.) and thus evaluates to True.

Here's a slight modification to your code, using negative indices to count back from the end of the array. For example, -2 is the same as n-2 when n is the length of the array.

I've also thrown in a little syntactic sugar at the end, using python's ternary operator.

def isSorted(arr):

    if len(arr) < 2:
        return True

    elif arr[-2] > arr[-1]:
        return False

    return isSorted(arr[:-1])

arr = [1,9,9,4,5]


print("yes" if isSorted(arr) else  "no")

CodePudding user response：

def isSorted(arr):

    n = len(arr)
    if n == 0 or n == 1:
        return True

    elif arr[n-2] > arr[n-1]:
        return False

    return isSorted(arr[0:n-1])

arr = [1,9,9,4,5]
#isSorted(arr)

#You should use "if isSorted(arr):" instead of "isSorted(arr)".
if isSorted(arr):

    print("yes")
else:

    print("no")

CodePudding user response：

A recursive approach can be implemented like this:

def isSorted(lst):
    if len(lst) < 2:
        return True
    return False if lst[1] < lst[0] else isSorted(lst[1:])

However, it's going to be slow compared with:

lst == sorted(lst)

...due to the efficient implementation of the sort() function

CodePudding user response：

As others have pointed out, there are non-recursive solutions which will outperform recursive implementations.

Having said that, if you insist on using recursion you should seek approaches that will not give you a stack overflow with larger arrays. Solutions which whittle the size of the problem down one element at a time will cause stack overflow on arrays that are larger than ~1000 elements. To avoid this, use an approach which cuts the problem size in half at each level of the recursion. The following algorithm does this:

def isSorted(ary):
    if len(ary) < 2:
        return True
    mid = len(ary) // 2
    return (ary[mid-1] <= ary[mid]) and isSorted(ary[:mid]) and isSorted(ary[mid:])

The logic is:

Arrays of length less than 2 are trivially considered sorted, so return True if this is the case;
Otherwise, find the mid-range value which will split the array into two sub-arrays which differ in length by no more than one;
The array is sorted if and only if the last element of the first sub-array is ≤ the first element of the second subarray, and both sub-arrays are sorted.

Since and is used, short-circuiting can occur. The recursive stack size is O(log(len(ary)).

As Mark pointed out, the reason you always get "yes" is because isSorted, without an argument, is a reference to the function and is considered "truthy" in python.

CodePudding user response：

Simply add the parameters to the function in the if statement:

if isSorted(arr):
    print("yes")
else
    print("no")