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])
The basic test is to see if L[i] is larger than every element of L[:i] and equal to the smallest element of L[i:]. There are lots of ways to do that. We exhibit an efficient method that only makes two passes through the list.
(For anyone curious or knowledegable about analysis of algorithms, there's a straightforward $O(n^2)$ algorithm, whereas this is a much more efficient $O(n)$ algorithm.)
def already_partitioned_indices(L):
"""
Return all indices `i` such that `L` is already
partitioned at `L[i]`.
"""
n = len(L)
# forward_maxes[i] will hold max(L[:i+1])
# initially it's a copy of L
forward_maxes = L[:]
# backward_mins[i] will hold min(L[i:])
# initially it's a copy of L
backward_mins = L[:]
# Fill forward_maxes with one pass through L
for i in range(n):
if i and forward_maxes[i-1] > L[i]:
forward_maxes[i] = forward_maxes[i-1]
# Fill backward_mins with one pass through L
# (from right to left)
for i in reversed(range(n)):
if i+1 < n and L[i] > backward_mins[i+1]:
backward_mins[i] = backward_mins[i+1]
# An index i is already partitioned if two
# conditions hold:
# (1) L[i] is bigger than the max of L[:i]
# (2) L[i] is equal to the min of L[i:]
# These are equivalent to
# (1) L[i] is greater than forward_maxes[i-1]
# (2) L[i] is equal to backward_mins[i]
return [ i for i in range(n) if
(i==0 or (L[i] > forward_maxes[i-1])) # (1)
and
L[i] == backward_mins[i] ] # (2)
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.
# Taken from sorts.py (comments abbreviated)
def partition(L, start, end):
"""
Partition the part of list `L` between indices `start` and `end`
(including `start` but not including `end`) in place, using the
item at index `end-1` as the pivot.
Returns the index where the pivot is after partitioning.
"""
# scan through `L[start:end]` looking for small items
dst = start
pivot = L[end - 1]
for src in range(start, end):
if L[src] < pivot:
L[src], L[dst] = L[dst], L[src]
dst += 1
L[end - 1], L[dst] = L[dst], L[end - 1]
return dst
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`.
"""
# fill in default value of end
if end == None:
end = len(L)
if end - start <= 1: # already sorted
return
# search for known pivot we can use, preferring one close
# to the middle of this part of the list if possible
m = (start + end)//2 # ideal pivot: middle
k = None # best already partitioned index found so far
for i in known_pivot_indices:
if i >= start and i < end: # i lies in the right range
if k == None or abs(i-m) < abs(k-m):
# i is either the first we've seen
# or it's closer to the middle than the
# previous best. Use it.
k = i
# if no existing partitioned index is found, create one
if k == None:
k = partition(L, start, end)
# CRITICALLY, after partitioning a part of the list
# that doesn't contain any of the already
# partitioned indices in `known_pivot_indices`,
# all the indices in that list are still valid,
# i.e. the list is still partitioned at them.
# recursion
hinted_quicksort(L, start, k, known_pivot_indices)
hinted_quicksort(L, k + 1, end, known_pivot_indices)
# return
return