q7_supplementary.py

def SelectPivotPair(L):
    """Return a pair (P0,P1) of pivot elements

    Select 5 distinct random elements from L, sort them,
    and let P0 be the second smallest and P1 the
    second largest of those 5 elements.
    """

def ThreePartition(L,P0,P1):
    """Return a triple (L0,L1,L2) of sublists of L

    L0 consists of all elements of L smaller or equal P0,
    L1 of all elements of L larger than P0 but smaller or
    equal P1, and L2 of all elements of L larger than P1
    """

def ThreeWayQuickSort(L):
    """Return a sorted version of L

    Use SelectPivotPair, ThreePartition and recursive
    calls to sort L.
    """

# simple tests

assert SelectPivotPair([5,4,3,2,1]) == (2,4)

assert ThreePartition([3,2,1],1,2) == ([1],[2],[3])

assert ThreeWayQuickSort([12,11,10,9,8,7,1,2,3,4,5,6]) == [1,2,3,4,5,6,7,8,9,10,11,12]