# This function is for testing, do not modify
def check(actual, expected):
if expected != actual:
print(
f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
def sort2(L):
## Your code goes here
pass
check(sort2([37, 9]), [9, 37])
check(sort2([1, 29]), [1, 29])
Function should return the value [9, 37], it is returning the value None Function should return the value [1, 29], it is returning the value None
Write a function sort4
that can sort a list of 4 elements. The function should make two calls to sort2
where sort2
sorts a list of size 2.
def sort4(L):
L_first_sorted = sort2(L[0:2])
L_last_sorted = sort2(L[2:4])
#
# do something to return a sorted list
#
sort2([1,4,3])
[1, 3, 4]
L = [5, 2, 1, 6]
check(sort4(L), [1, 2, 5, 6])
M = [4, 3, 2, 1]
check(sort4(M), [1, 2, 3, 4])
Write a function sort32
that sorts a list of 32 elements. The function should make two recursive calls to a provided function sort16
sort16 = sorted
def sort32(L):
L_first_sorted = sort16(L[0:16])
L_last_sorted = sort16(L[16:32])
#
# do something to return a sorted list
#
# TEST_CASE
L = [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18,
17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
check(sort32(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, 31, 32])
list1 = [1, 3, 5, 7, 9]
list2 = [2, 4, 6, 8, 10]
## Your code goes below here
What if we remove the last few elements from list1
? What changes can you make for your code to work?
list1 = [1, 3, 5, 7, 9]
list2 = [2, 4, 6]
## Your code goes below here
Write a function combine_sorted
that takes in two sorted lists and gives a combined sorted list.
def combine_sorted(list1, list2):
# Your code goes here
pass
Write a function merge_sort
that will sort a list of any size. The function should make two recursive calls to itself and use the combine_sorted
function you implemented in question 2.
def merge_sort(L):
#
# do something here
#
L_first_sorted = merge_sort(
L[0:int(len(L)/2)])
L_last_sorted = merge_sort(
L[int(len(L)/2):len(L)])
#
# do something to return a sorted list
return combine_sorted(L_first_sorted, L_last_sorted)
L = [23, 10, 5, 1, 4]
check(merge_sort(L), [1, 4, 5, 10, 23])
M = [4, 3, 2, 1]
check(merge_sort(M), [1, 2, 3, 4])
Write a function merge_sort2
that uses the previous function sort_almost_sorted
. Instead of calling the function on smaller lists, it uses indices to keep track of where it is sorting.
def merge_sort2(L):
return merge_sort2_h(L, 0, len(L) - 1)
def merge_sort2_h(L, start, end):
#
# do something here
#
## define middle index
##mid = sth
L = merge_sort2_h(L, start, mid)
L = merge_sort2_h(L, mid + 1, end)
#
# do something to return a sorted list
return sort_almost_sorted(L)