pythonsortingcounterswappython-decorators

Python: Decorator to count swaps in sorting algorithms


I want to write a decorator that will count the number of swaps in a sorting algorithm. I created a swap function to swap numbers and a decorator that counts each call to this function. The issues I've encountered are as follows: when I count the number of calls for multiple algorithms, it counts the "swaps" for each of them and sums them up. Another issue is that each "swap" is printed in the console. Below, I'm including the decorator, swap and a sample algorithm.

Decorator:

def swapCounter(func):
    def counter(*args, **kwargs):
        counter.calls += 1
        print(f"Swaps {counter.calls}")
        return func(*args, **kwargs)
    counter.calls = 0
    return counter

Swap:

def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]

Sample sorting algorithm:

def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(0, len(arr)-i-1):
            if arr[j] > arr[j+1]:
                swap(arr, j, j+1)

    return arr

I tried adding flags in the decorator and in the swap function. In swap, the flag would be set at the end, allowing the decorator to reset at the right moment. However, this didn’t yield any results: AttributeError: 'function' object has no attribute 'calls'

def swapCounter(func):
    def counter(*args, **kwargs):
        counter.calls+=1
        if kwargs.get("flag")==True:
            print(f"Swaps {counter.calls}")
            counter.calls = 0
            return func(*args, **kwargs)
    return counter
def swap(arr=None, i=None, j=None, flag=None):
        arr[i], arr[j] = arr[j], arr[i]
def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(0, len(arr)-i-1):
            if arr[j] > arr[j+1]:
                swap(arr, j, j+1)

    swap(True)

Solution

  • You have a few minor problems in your implementation. Firstly, in swapCounter you would need to set counter.calls = 0 outside of the counter function so that the attribute is defined from outside of the scope of the function. Also, I think your method of resetting the counter can be done a bit more elegantly if we remove the flag from the decorator and instead attach a reset method to the decorator function.

    Take a look at this swapCounter function:

    def swapCounter(func):
    
        def counter(*args, **kwargs):
            # Increment the swap counter on each call
            counter.calls += 1
            # Only call the original function; no printing here
            return func(*args, **kwargs)
    
        # Attribute to hold the number of swap calls
        counter.calls = 0
    
        # Method to reset and retrieve count for a new sorting run
        def reset_count():
            swap_count = counter.calls
            counter.calls = 0
            return swap_count
    
        # Attach the reset method to the decorator function
        counter.reset_count = reset_count
        return counter
    

    Now, we can simply add the decorator to the swap function as follows:

    @swapCounter
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]
    

    And then your sort function would look something like this:

    def bubbleSort(arr):
        for i in range(len(arr)):
            for j in range(0, len(arr) - i - 1):
                if arr[j] > arr[j + 1]:
                    swap(arr, j, j + 1)
        # Print the total number of swaps for this run
        print(f"Total Swaps in Bubble Sort: {swap.reset_count()}")
        return arr
    

    Also, note that the final line return arr is a bit redundant as your swap function modifies the array passed to the function so for example:

    arr1 = [5, 3, 8, 4, 2]
    arr2 = bubbleSort(arr1)
    assert arr1 == arr2 # This doesn't give an error as the arrays are now the same