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

MCS 275 Spring 2023 Homework 7

  • Course Instructor: David Dumas

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work.

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 28, 2023.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Content

This assignment is about recursive sorting algorithms.

Resources you may consult

Most relevant:

Less likely to be relevant, but also allowed:

Point distribution

This homework assignment has 2 problems, numbered 2 and 3. The grading breakdown is:

Points Item
3 Autograder
6 Problem 2
6 Problem 3
15 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 2: Initial sorted segment length

Submit all work for this problem in a file called hwk7prob2.py.

Write a function ISS_len(L) that takes a nonempty list L whose elements support comparison, and which returns the largest integer k such that L[:k] is already sorted. (We then refer to L[:k] as the initial sorted segment of L, since it's the longest initial segment of L that is sorted.)

Since a 1-element list is always sorted, the returned value will always be greater than or equal to 1.

Don't call any sorting function to achieve this; instead, search through the list and look for the first place where an element is larger than the one after it (or if that never occurs). You can determine k from this information.

Problem 3: Quergesort

Submit all work for this problem in a file called hwk7prob3.py.

Suppose you can't decide between quicksort and mergesort, so you decide to combine them into a single sorting algoritm that operates as quicksort at the top level of recursion (partitioning and calling itself on the pieces), as mergesort at the next level (cutting into pieces of equal size, recursively sorting them, then merging the results), then quick again, then merge again, all the way down. This problem asks you to write such a "quergesort" function.

Since mergesort was written as a transformation in class (returns a new list) while quicksort was written as a mutation (reorders elements of the original list), we need to decide on one of those to use throughout this new sort. We choose to make it a mutation, so it returns nothing and modifies the list given as an argument.

The quergesort algorithm, more precisely, is:

  • Like quicksort, it accepts a list L and start and end indices specifying the part to operate on.
  • The function also accepts a mode argument with default value "quick". This argument controls which mode the function is currently working in.
  • In mode "quick", the function does the following:
    • If the list has 0 or 1 elements, returns. Otherwise...
    • Partitions the part of the list it's working on
    • Calls quergesort with mode="merge" on the part before the pivot
    • Calls quergesort with mode="merge" on the part after the pivot
  • In mode "merge", the function does the following:
    • If the list has 0 or 1 elements, returns. Otherwise...
    • Decides on an index that would split this part of the list into roughly equal-size parts.
    • Calls quergesort with mode="quick" to operate on the first part
    • Calls quergesort with mode="quick" to operate on the second part
    • Uses merge to merge the two now-sorted parts into a new list
    • Copies the values in the new merged, sorted list back into the part of the original list we're supposed to operate on.

Notice that in mode "quick", the next calls use mode "merge", and vice versa, so the function always switches modes at the next level of recursion.

Use the following function definition line and docstring.

In [ ]:
def quergesort(L,start=0,end=None,mode="quick"):
    """
    Recursively sort `L` in place using alternating rounds of partioning (like 
    quicksort) and split+merge (like mergesort).
    """

You can copy the functions merge and partition from the course sample code in sorts.py directly into your solution file. You don't need to write those functions again, and should call those functions as part of your solution.

Do not call quicksort or mergesort from this function. Only call:

  • Built-in functions
  • partition
  • merge
  • quergesort

Revision history

  • 2023-02-23 Initial publication