This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 20, 2024.
Collaboration is prohibited, and while working on this you should only consult the resources (books, online, etc.) listed below.
This assignment corresponds to Worksheet 6, which is about comparison sorts.
The materials you may refer to for this homework are:
This homework assignment has two problems. The grading breakdown is:
| Points | Item |
|---|---|
| 4 | Autograder syntax checks (problem 1) |
| 5 | Problem 2 |
| 5 | Problem 3 |
| 14 | Total |
Ask your instructor or TA a question by email, in office hours, or on discord.
Work in hwk6prob2.py.
Recall that in our implementation of quicksort, we wrote a partition function that uses the last element of the list (or portion thereof) as a pivot. However, as we discussed, one can partition a list using any item as a pivot. In worksheet 6 you explored this a bit.
Now, sometimes it may happen that a list is already partitioned at a certain index. For example, if we consider the list
L = [6, 7, 8, 22, 9, 20, 5, 1, 23, 43, 71, 63]
# index : 0 1 2 3 4 5 6 7 8 9 10 11
Then we can see it is already partitioned at index 8 (i.e. L[8]=23 is bigger than everything before it, and less than or equal to everything after it).
Similarly the example list above is also already partitioned at index 9, as you can check.
Write a function
def already_partitioned_indices(L):
that takes a list L whose items support comparison, and which returns a list of all the indices i such that L is already partitioned with pivot L[i].
The list L should not be modified by calling this function.
Sample return values:
already_partitioned_indices([6,7,8,22,9,20,5,1,23,43,71,63])
already_partitioned_indices([15,8,4,16,42,23])
already_partitioned_indices([2,4,8,16,32,64])
Work in hwk6prob3.py.
Be sure to read problem 2 first.
The function already_partitioned_indices you wrote in problem 2 probably takes as long to run as sorting the list L, and for that reason you wouldn't want to use it as part of a sorting algorithm.
However, imagine you were given a list L and also given some information about indices where it is already partitioned, e.g. you might be asked
"I have a list
L. It has 100 elements, and I happen to know that it is already partitioned at indices 4 and 62."
Write a version of quicksort that takes advantage of this kind of information as follows: Any time the usual quicksort would call partition, this "hinted" version of quicksort will first check to see if there is an index where we already know the list is partitioned that can be used instead. If not, it falls back to calling partition as usual.
Use the following function name, argument list, and docstring:
def hinted_quicksort(L,start=0,end=None,known_pivot_indices=[]):
"""
In-place quicksort that operates on the part of `L`
between index `start` and index `end`, not including
the latter. If omitted, `start` is taken to be the
start of the list, and `end` is taken to be beyond
the end of the list.
If given, the optional `known_pivot_indices` should be a
list of indices in `L` at which the list is known to
already be partitioned. There is no guarantee that every
such index is included in that argument, nor that all the
indices given lie between `start` and `end`.
"""
You're welcome to freely use of any of the code from sorts.py or worksheet 6 as a starting point for your answer.
Remember, do not call already_partitioned_indices in your answer to problem 3. This problem does not involve finding already partitioned indices, but rather it focuses on using that kind of information as part of a sorting process.