A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

Quiz 7 Solutions

MCS 275 Spring 2021 - Emily Dumas

Solutions by Jennifer Vaccaro

Instructions:

Deadline

This quiz must be submitted in Gradescope by 12:00pm CST on Tuesday, March 2, 2021.

Topic

The course topics corresponding to this quiz are recursion with backtracking and sorting algorithms.

Resources you are allowed to consult

Quizzes are INDIVIDUAL, closed book, and only allow access to specified resources. For this quiz you can access:

Point distribution

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

(No problem number 1, as usual)

The points assigned by the autograder based on syntax and docstring checking will be listed as problem 1 in Gradescope.

Problem 2: Lumpsort

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:

  • If the list is short enough, call shortsort to sort it.
  • Otherwise, split the list in half and handle each half with a recursive call to 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:

In [ ]:
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.

In [1]:
# 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()
In [2]:
# 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.

In [3]:
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)
BEFORE: L = [4, 3, 7, 5, 0, 2, 6, 8, 9, 1]
shortsort2 called on list [4, 3]
shortsort2 called on list [7]
shortsort2 called on list [5, 0]
shortsort2 called on list [2, 6]
shortsort2 called on list [8]
shortsort2 called on list [9, 1]
AFTER: L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [4]:
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)
BEFORE: L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8]
shortsort2 called on list [10]
shortsort2 called on list [0, 2]
shortsort2 called on list [1]
shortsort2 called on list [7, 4]
shortsort2 called on list [6]
shortsort2 called on list [5, 3]
shortsort2 called on list [9]
shortsort2 called on list [11, 8]
AFTER: L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
In [5]:
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)
BEFORE: L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8, 12]
shortsort_fake called on list [10, 0, 2]
shortsort_fake called on list [1, 7, 4]
shortsort_fake called on list [6, 5, 3]
shortsort_fake called on list [9, 11]
shortsort_fake called on list [8, 12]
AFTER: L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
In [6]:
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)
BEFORE: L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8, 12]
shortsort_fake called on list [10, 0, 2]
shortsort_fake called on list [1, 7, 4]
shortsort_fake called on list [6, 5, 3]
shortsort_fake called on list [9, 11, 8, 12]
AFTER: L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
In [34]:
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)
BEFORE: L = [10, 0, 2, 1, 7, 4, 6, 5, 3, 9, 11, 8, 12]
shortsort_fake called on list [10]
shortsort_fake called on list [0]
shortsort_fake called on list [2]
shortsort_fake called on list [1]
shortsort_fake called on list [7]
shortsort_fake called on list [4]
shortsort_fake called on list [6]
shortsort_fake called on list [5]
shortsort_fake called on list [3]
shortsort_fake called on list [9]
shortsort_fake called on list [11]
shortsort_fake called on list [8]
shortsort_fake called on list [12]
AFTER: L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]