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()
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)