

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

Dual Pivot Quicksort



In [ ]:

    
def sort(L):
    if len(L) <= 1:
        return L
    x, y, R    = L[0], L[-1], L[1:-1]
    p1, p2     = min(x, y), max(x, y)
    L1, L2, L3 = partition(p1, p2, R)
    if p1 == p2:
        return sort(L1) + [p1] + L2 + [p2] + sort(L3)
    else:
        return sort(L1) + [p1] + sort(L2) + [p2] + sort(L3)



In [ ]:

    
def partition(p1, p2, L):
    if L == []:
        return [], [], []
    x, R       = L[0], L[1:]
    R1, R2, R3 = partition(p1, p2, R)
    if x < p1:
        return [x] + R1, R2, R3
    if x <= p2:
        return R1, [x] + R2, R3
    else:
        return R1, R2, [x] + R3



In [ ]:

    
partition(5, 13, [1, 19, 27, 2, 5, 6, 4, 7, 8, 5, 8, 17, 13])



In [ ]:

    
sort([1, 19, 27, 2, 5, 6, 4, 7, 8, 5, 8, 17, 13])



In [ ]: