Python recursive def separate(p : callable, l : [object]) -> ([object],[object])
ID: 3835888 • Letter: P
Question
Python recursive
def separate(p : callable, l : [object]) -> ([object],[object]):
a = []
b = []
if l == []:
return (a,b)
else:
a,b = separate(p, l[1:])
if p(l[0]):
a = [l[0]] + a
else:
b = b + [l[0]]
return (a,b)
def sort(l : [object]) -> [object]:
4. (4 pts) Define a recursive function named sort, it is passed alist of comparable values (e.g., all ints or all strs) as an argument, it returns a new list (constructing a new one, not mutating the argument) with every value in the original list, but ordered non-descending. You must code the following algorithm. For any non-empty argument list, use the first value in the list to separate the rest of the list (call separate from question 3) into two lists: those with values the first value and those with values the first value; don't include this first value in either list: the sum of the lengths of the two resulting lists should be one less than the length of the argument list). Note: all the values in the first list are strictly all the values in the second list Recursively call sort on each of these two lists and use list concatenation to return a single list that contains the sorted values in the first list (the smaller ones), followed by the value used to separate the list, followed by the sorted values in the second list (the larger ones). Again, as in question 3, for the non-base case, first call separate and bind the result (and never change that binding), then determine what result to return, using the binding and recursive calls to sort. So, sort [4,5,3,1,2,7,6]) would call separate first to compute the lists [3,1, 21 and [5,7,6 (note that 4, the first value in the list, is used to do the separation, and is not in either resulting list) When sorted recursively, these lists are 1,2,3] and [5,6, 7]. Concatenating these lists, with the separator value between them, results in returning the list [1,2,3,4,5,6,71 (the 4 is put in the result list, in the correct place). Your function should run to completion with no noticeable delay. Of course you should not use any built-in Python methods for sortingExplanation / Answer
def sort(l : [object]) -> [object]:
pass
def sort(l):
''' recursive function when passed a list; it returns a new list (not mutating
the passed one) with every value in the original list, but ordered in non-
descending order. '''
if len(l) == 0:
return []
else:
(before, after) = separate(lambda i: i < l[0], l[1:])
return sort(before) + [l[0]] + sort(after)
# Test sort
e-->sort([1,2,3,4,5,6,7])-->[1, 2, 3, 4, 5, 6, 7]
e-->sort([7,6,5,4,3,2,1])-->[1, 2, 3, 4, 5, 6, 7]
e-->sort([4,5,3,1,2,7,6])-->[1, 2, 3, 4, 5, 6, 7]
e-->sort([1,7,2,6,3,5,4])-->[1, 2, 3, 4, 5, 6, 7]
c-->l = [i+1 for i in range(30)]
c-->random.shuffle(l)
c-->l = sort(l)
e-->l-->[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
if __name__ == '__main__':
import driver, random
print(' driver testing with batch_self_check:')
driver.driver() # type quit in driver to return and execute code below
from goody import irange
from predicate import is_positive
print('Testing separate')
print(separate(is_positive,[]))
print(separate(is_positive,[1, -3, -2, 4, 0, -1, 8]))
print(separate(is_prime,[i for i in irange(2,20)]))
print(separate(lambda x : len(x) <= 3,
'to be or not to be that is the question'.split(' ')))
print(' Testing is_sorted')
print(is_sorted([]))
print(is_sorted([1,2,3,4,5,6,7]))
print(is_sorted([1,2,3,7,4,5,6]))
print(is_sorted([1,2,3,4,5,6,5]))
print(is_sorted([7,6,5,4,3,2,1]))
print(' Testing sort')
print(sort([1,2,3,4,5,6,7]))
print(sort([7,6,5,4,3,2,1]))
print(sort([4,5,3,1,2,7,6]))
print(sort([1,7,2,6,3,5,4]))
l = [i+1 for i in range(30)]
random.shuffle(l)
print(l)
print(sort(l))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.