Solution [Do NOT peek!]






















































































def qsort(A):
    def qsort_iter(L, start, stop):
        if start >= stop:
            return
        wall = start
        pivot = stop
        for i in range(start, stop):
            if L[i] < L[pivot]:
                L[wall], L[i] = L[i], L[wall]
                wall += 1
        L[wall], L[pivot] = L[pivot], L[wall]
        qsort_iter(L, start, wall - 1)
        qsort_iter(L, wall + 1, stop)
    
    qsort_iter(A, 0, len(A)-1)

    
A = [1, 3, 2, 5, 7, 6, 4]
qsort(A)
print(A)




def qs_outtaplace(A):
    if len(A)<=1:
        return A
    else:
        left, right = [], []
        for i in range(1, len(A)):
            if A[i] < A[0]:
                left += [A[i]]
            else:
                right += [A[i]]
        return qs_outtaplace(left)+[A[0]]+qs_outtaplace(right)
        
# Test cases. Delete the appropriate #s to test
#Worst case
A = [1, 2, 3, 4, 5, 6, 7]
print(qs(A))
# Best case
A = [7, 6, 5, 4, 3, 2, 1]
print(qs(A))



ċ
qs.py
(1k)
Dean Ang Gmail,
Sep 24, 2015, 11:18 AM
Comments