counter = 0

"""
 This is just a "wrapper" for the
 calls to quicksort, to
 *  Make the call easier to type
 *  Output the number of comparisons """
def qs(A):
    global counter
    counter = 0
    Quicksort(A, 0, len(A)-1)
    print(counter, "comparisons.")
    print("array =", A)

# p = start and r = end of the portion to "Quicksort"
def Quicksort(A, p, r):
    if p <= r:
        q = Partition(A, p, r)
        Quicksort(A, p, q - 1) #recursively sort the left half
        Quicksort(A, q + 1, r) #recursively sorr the right half

def Partition(A, p, r):
    global counter
    x = A[r]   #last element in array
    i = p-1
    for j in range(p, r):
        counter = counter + 1
        if A[j] < x:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[r], A[i+1] = A[i+1], A[r]
    return i+1