This quiz must be submitted in Gradescope by 12:00pm CST on Tuesday, March 2, 2021.
The course topics corresponding to this quiz are recursion with backtracking and sorting algorithms.
Quizzes are INDIVIDUAL, closed book, and only allow access to specified resources. For this quiz you can access:
Instead of the usual 2 or 3 problems, this quiz has just one problem. The manual review of that problem for correctness is worth 8 points. Therefore, the final grading breakdown is:
| Points | Item |
|---|---|
| 3 | autograder |
| 8 | problem 2 |
| 11 | total |
The points assigned by the autograder based on syntax and docstring checking will be listed as problem 1 in Gradescope.
Recall that mergesort uses recursive calls to repeatedly split a list into halves until the pieces are so tiny that they are already sorted (i.e. have at most one element). It then uses merges to build successively larger sorted lists.
Imagine you are instead in a situation where a function shortsort has been provided that can sort short lists, but not long ones. This can be turned into a sorting algorithm for lists of any size, which we'll call lumpsort, as follows:
shortsort to sort it.lumpsort. Then, merge the two sorted halves with merge_sorted_lists.(The reason I've called it "lumpsort" is that it only breaks a list into "lumps" of a certain maximum size, whereas mergesort always pulverizes a list into atoms.)
In a file called quiz7prob2.py, implement this algorithm in a function lumpsort with the following function definition:
def lumpsort(L,shortsort,shortmax):
"""Sort a list using the lumpsort algorithm. Arguments:
`L` : The list to be sorted. Modified in place.
`shortsort` : A function that accepts a single argument, a list,
and sorts it in place. The list must have length
at most `shortmax`.
`shortmax` : A positive integer that is the longest length of
list that `shortsort` can handle."""
In order to receive full credit, your lumpsort must use exactly the argument list given here, and must follow the algorithm described above (in particular it must be recursive).
You can use code from our implementation of mergesort as part of your solution, but make note of it if you do so.
To make testing your function easier, here are two examples of shortsort functions you might try it with. You can use these for testing, but don't include them in the quiz7prob2.py you submit.
# Both of these contain print() debugging statements that can be
# removed if you prefer.
def shortsort2(L):
"""Sort a list of length <=2 in place"""
print("shortsort2 called on list",L)
if len(L)<2:
return
if L[0]>L[1]:
L[0],L[1] = L[1],L[0]
def shortsort_fake(L):
"""Sort a list of any length. Intended to be used
as a drop-in for the `shortsort` argument of `lumpsort`.
Can be used with any value of `shortmax`."""
print("shortsort_fake called on list",L)
L.sort()
# MCS 275 Quiz 7 Problem 2
# Jennifer Vaccaro
# I wrote lumpsort myself, and pulled merge_sorted_lists from mergesort.py
# From mergesort.py course example code
def merge_sorted_lists(L1,L2,L):
"""Take sorted lists L1 and L2 and a list L whose length
is len(L1)+len(L2). Merge L1 and L2, maintaining sorted
order, storing the results in L. No return value."""
i1 = 0 # position in L1
i2 = 0 # position in L2
i = 0 # position in L
while i1<len(L1) and i2<len(L2):
if L1[i1] <= L2[i2]:
# Take from L1
L[i] = L1[i1]
i1 += 1
else:
# Take from L2
L[i] = L2[i2]
i2 += 1
i += 1
while i1<len(L1):
L[i] = L1[i1]
i1 += 1
i += 1
while i2<len(L2):
L[i] = L2[i2]
i2 += 1
i += 1
# My own code
def lumpsort(L,shortsort,shortmax):
"""Sort a list using the lumpsort algorithm. Arguments:
`L` : The list to be sorted. Modified in place.
`shortsort` : A function that accepts a single argument, a list,
and sorts it in place. The list must have length
at most `shortmax`.
`shortmax` : A positive integer that is the longest length of
list that `shortsort` can handle."""
# If shortsort can handle the size of L, then great!
if len(L) <= shortmax:
shortsort(L)
# No return necessary, we modify L directly
else:
# If L is longer, then split it into two smaller lists.
halfway = len(L) // 2
L1 = L[:halfway]
L2 = L[halfway:]
# Recursively call lumpsort on each of the smaller lists, and with the same shortsort and shortmax
lumpsort(L1,shortsort,shortmax)
lumpsort(L2,shortsort,shortmax)
# Recombine the sorted pieced using merge_sorted_lists
merge_sorted_lists(L1,L2,L)
# No return necessary, since we modify L directly
And here are some examples of calling lumpsort with these functions, and the expected output. Notice the list is broken into pieces of a specified maximum size, and the provided shortsort function is called for those pieces.
Again, code like the examples below may help you test your function, but don't submit it. Only submit lumpsort itself and whatever merge function it calls.
L = [4, 3, 7, 5, 0, 2, 6, 8, 9, 1]
print("BEFORE: L =",L)
# Lumps of size 2 will be handled by shortsort2
lumpsort(L,shortsort2,2)
print("AFTER: L =",L)
L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8]
print("BEFORE: L =",L)
# Lumps of size 2 will be handled by shortsort2
lumpsort(L,shortsort2,2)
print("AFTER: L =",L)
L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8, 12]
print("BEFORE: L =",L)
# Lumps of size 3 will be handled by shortsort_fake
lumpsort(L,shortsort_fake,3)
print("AFTER: L =",L)
L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8, 12]
print("BEFORE: L =",L)
# Lumps of size 4 will be handled by shortsort_fake
lumpsort(L,shortsort_fake,4)
print("AFTER: L =",L)
L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8, 12]
print("BEFORE: L =",L)
# Lumps have maximum size 1, meaning they never need
# any sorting. In this case lumpsort just recreates
# mergesort.
lumpsort(L,shortsort_fake,1)
print("AFTER: L =",L)