def swap(A,i,j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp

CompCount = [0,0,0]

def partitionRight(A, left, right):
    p = A[right]
    i = left
    for j in range(left,right):
        CompCount[1] += 1
        if A[j] < p:
            swap(A,i,j)
            i += 1
    swap(A,right,i)
    return i

def partitionLeft(A, left, right):
    p = A[left]
    i = left + 1
    for j in range(left+1,right):
        CompCount[0] += 1
        if A[j] < p:
            swap(A,i,j)
            i += 1
    swap(A,left,i-1)
    return i-1

##def partitionRight(A, left, right):
##    p = A[right]
##    i = right-1
##    for j in range(right-1, left-1, -1):
##        CompCount[1] += 1
##        if A[j] > p:
##            swap(A,i,j)
##            i -= 1
##    swap(A,right,i+1)
##    return i+1

def quickSortL(array, left, right):
    if left < right:
        i = partitionLeft(array, left, right)
        quickSortL(array, left, i)
        quickSortL(array, i+1, right)

def quickSortR(array, left, right):
    if left < right:
        i = partitionRight(array, left, right)
        print "recursing on left array from",left,"to",i-1
        quickSortR(array, left, i-1)
        print "recursing on right array from",i+1,"to",right
        quickSortR(array, i+1, right)

def tester(filename):
    CompCount[0] = 0
    file1 = open(filename)
    testlist2 = []
    for line in file1:
        testlist2.append(int(line))
    file1.close()
    print "initial:"
    print testlist2
    print
    copy1 = testlist2[:]
    copy2 = testlist2[:]
    print "_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-"
    quickSortL(copy1, 0, len(copy1))
    print copy1
    quickSortR(copy2, 0, len(copy2)-1)
    print copy2
    if copy1 == copy2: print "sort results match."
    else: print "sort results don't match."
    print
    print "First element as pivot : %d comparisons" % CompCount[0]
    print "Final element as pivot : %d comparisons" % CompCount[1]
    print "_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-"
    print

tester("TestCase2.txt")