I am trying to check if a list is sorted using recursion in python. Returns true if sorted, False if not sorted.
def isSorted(L):
if len(L) < 2:
return True
Now, I am not sure what I should be doing next.Please help!
-
You should write a unit test for this :) And then assert that a list of x items is in the correct order.Henrik Andersson– Henrik Andersson2014-05-05 05:37:23 +00:00Commented May 5, 2014 at 5:37
Add a comment
|
1 Answer
Check first two items.
If they are ordered, check next items using recursion:
def isSorted(L):
if len(L) < 2:
return True
return L[0] <= L[1] and isSorted(L[1:])
Side note The function can be expression as a single expression as thefourtheye commented:
return len(L) < 2 or (L[0] <= L[1] and isSorted(L[1:]))
3 Comments
thefourtheye
return len(L) < 2 or (L[0] <= L[1] and isSorted(L[1:]))?
lightalchemist
+1. Could also avoid the list copy by taking in an extra argument for the index of the current element and increment this index in the recursive calls. Then define a wrapper to pass in the initial index set to 0. Base case will change to whether idx >= len(L) -1. But this captures the gist. Nice.
John La Rooy
If you split the list in half at each step, the recursion depth will be log2(n)