.py files containing your work.This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 28, 2023.
Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.
This assignment is about recursive sorting algorithms.
Most relevant:
Less likely to be relevant, but also allowed:
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.
Ask your instructor or TA a question by email, in office hours, or on discord.
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.
def ISS_len(L):
"""Returns length of initial segment of L with fully sorted entries"""
if len(L) == 1:
return 1
k = 1
while k <= len(L):
if L[k-1] <= L[k]:
k += 1
else:
break
return k
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:
L and start and end indices specifying the part to operate on.mode argument with default value "quick". This argument controls which mode the function is currently working in."quick", the function does the following:quergesort with mode="merge" on the part before the pivotquergesort with mode="merge" on the part after the pivot"merge", the function does the following:quergesort with mode="quick" to operate on the first partquergesort with mode="quick" to operate on the second partmerge to merge the two now-sorted parts into a new listNotice 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.
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:
partitionmergequergesortdef 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).
"""
if end == None:
end = len(L) # Default value of `end`
if end - start <= 1: # Note that len(L) never changes - so we instead need to use start and end
return
if mode == "quick":
m = partition(L, start, end) # `m` is the pivot index
quergesort(L, start, m, mode="merge") # Quergesort everything in front of the pivot
quergesort(L, m+1, end, mode="merge") # Quergesort everything after the pivot
else:
m = (start + end) // 2 # midpoint
quergesort(L, start, m, mode="quick")
quergesort(L, m, end, mode="quick")
# Replace the part of original list L that we're operating on
# with a merged version of the two sorted lists
merged_list = merge(L[start:m], L[m:end])
L[start:end] = merged_list
The folllowing code snippet can also be added to the module to help test our quergesort function. If quergesort does not fully sort any of the test lists, the tests will stop and produce an error. Otherwise, we will get a message that the tests have passed.
if __name__ == "__main__":
import random
num_random_tests = 10_000
print("*************")
print("* QUERGESORT *")
print("*************")
L = [7, 6, 2, 3, 5, 8, 1, 4]
print("\nVerbose test with input", L, "\n--BEGIN FUNCTION CALL--")
quergesort(L)
print("--END FUNCTION CALL--\nAfter quergesort, list contains", L)
print("\nTesting quergesort on", num_random_tests, "permutations of range(0,100):")
orig = list(range(100))
for _ in range(num_random_tests):
L = list(orig) # make a copy of `orig`
random.shuffle(L)
quergesort(L)
assert orig == L, "Sorted list was different from original.\n Original:\n{}\n Sorted: {}\n".format(orig, L)
print("PASS - All tested permutations correctly sorted.")