Quick Sort Comparison Counter in Python

Question

I have a fully functioning quick sort partitioning algorithm and I am trying to fit in a counter for every comparison made. This is giving me a challenge. Any hints as to where to put this counter?

def partition(mylist, start, end):
    pos = start
    for i in range(start, end):
        if mylist[i] < mylist[end]:
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos

def quicksort(mylist, start, end, c):
    if start < end:
        pos = partition(mylist, start, end)
        c= c+ (len(mylist) -1    )   
        quicksort(mylist, start, pos - 1, c)
        c= c+ (len(mylist) -1    )       
        quicksort(mylist, pos + 1, end, c)
        c= c+ (len(mylist) -1    )


count = (0)
quicksort(x, 0, len(x)-1, count)

Where x refers to a list of integers

Answer 1

You have only two places where a comparison happens explicitly, both are if statements, and you can put a counter increment right before those lines, for example:

counter = 0 # the global variable

def myfunc1():
    global counter
    counter = counter + 1
    if my < comparison:
         pass

def myfunc2():
    global counter
    counter = counter + 1
    if my < comparison:
         pass

print(counter)

This does not count the implicit comparisons in the mechanism of the for loop for example, but I don't think that's what you're intending to do.

Here is another kind of cute way you could pass around counter information, and avoid globals:

def myfunc1():
    myfunc1.counter += 1
    if 2 < 1:
         pass

def myfunc2():
    myfunc2.counter += 1
    if 1 < 2:
         pass

myfunc1.counter = 0
myfunc2.counter = 0

for f in (myfunc1, myfunc2):
    print("{} had {} comparisons".format(f.__name__, f.counter))

EDIT/NOTE: Some of the answers here use a parameter passed into each function to keep track of the counter. That is a valid approach as well, but really what we need is a much more general purpose approach (otherwise you are endlessly going to be passing around counters in the general case, and that is painful). In summary:

• Global variable (not good practice)
• Function attribute (not good practice)
• Passing extra parameter and returning extra parameter (painful, but better in general)
• Instance variable, and your functions are members of a class (but what if you don't want to use objects?)
• Perhaps a more generally applicable way, working example below:

Note that this uses decorators, meaning you can add any number of functions like less_than without making them understand the counting requirement.

def count(func):
    def inner(*args):
        inner.counter += 1
        return func(*args)
    inner.counter = 0
    return inner

@count
def less_than(op1, op2):
    return op1 < op2

def partition(mylist, start, end):
    pos = start
    for i in range(start, end):
        if less_than(mylist[i], mylist[end]):
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos

def quicksort(mylist, start, end):
    if less_than(start, end):
        pos = partition(mylist, start, end)
        quicksort(mylist, start, pos - 1)
        quicksort(mylist, pos + 1, end)


x = [3, 2, 5, 1, 0]
quicksort(x, 0, len(x)-1)
print(x)
print(less_than.counter)

You could further organize it by making a counter class that keeps track of any number of functions and all the times they are called, and removes the function attribute, storing the data in eg. a dictionary.

Answer 2

To improve further on some existing answers, unless you are trying to make this tail recursive (which doesn't work for quicksort anyways), you don't need to pass in the count value. Instead you can just maintain the invariant that each call to partition returns the count of all comparisons it has performed and each call to quicksort returns the count of all partitions that have been performed by it or any recursive calls within it.

Additionally, we can put the recursive implementation of quicksort into a helper function and wrap it in a nice function which only takes a list so we don't have to manually pass in the start and end indices.

Implementing this gives us the following:

def _partition(mylist, start, end):
    count = 0
    pos = start
    for i in xrange(start, end):
        count += 1
        if mylist[i] < mylist[end]:
            mylist[i], mylist[pos] = mylist[pos], mylist[i]
            pos += 1
    mylist[pos], mylist[end] = mylist[end], mylist[pos]
    return pos, count

def _quicksort(mylist, start, end):
    count = 0
    if start < end:
        pos, count = _partition(mylist, start, end)        
        count += _quicksort(mylist, start, pos - 1)
        count += _quicksort(mylist, pos + 1, end)
    return count

def quicksort(mylist, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(mylist) - 1
    return _quicksort(mylist, start, end)

x = [2,3,1]
count = quicksort(x)
print x, count

Answer 3

def partition(mylist, start, end, count):
    pos = start
    for i in range(start, end):
        count += 1
        if mylist[i] < mylist[end]:
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos, count

def quicksort(mylist, start, end, count):
    if start < end:
        pos, count = partition(mylist, start, end, count)        
        count = quicksort(mylist, start, pos - 1, count)
        count = quicksort(mylist, pos + 1, end, count)
    return count


x = [2,3,1]
count = quicksort(x, 0, len(x)-1, 0)
print x, count