Search code examples
pythonfunctionsortingnumbersinsertion-sort

How do I add a swap and comparisons counter in my code?


For a list of numbers, I am trying to sort them in ascending order. At the same time, I need to add a swap and comparison counter to my output. For the most part, how do I add the incrementation in my code? My code:

def insertion_sort(numbers):
    """Sort the list numbers using insertion sort"""
    # TODO: Count comparisons and swaps. Output the array at the end of each iteration.
    for i in range(1, len(numbers)):
        j = i
        # Insert numbers[i] into sorted part
        # stopping once numbers[i] is in correct position
        while j > 0 and numbers[j] < numbers[j - 1]:
            swap(numbers, j, j - 1)
            j -= 1

This is an insertion sorting method.


Solution

  • Split up the condition so you can separate the comparisons from the swaps.

    def insertion_sort(numbers):
        """Sort the list numbers using insertion sort"""
        comparisons = 0
        swaps = 0
        for i in range(1, len(numbers)):
            j = i
            # Insert numbers[i] into sorted part
            # stopping once numbers[i] is in correct position
            while j > 0:
                comparisons += 1
                if numbers[j] < numbers[j - 1]:
                    swap(numbers, j, j - 1)
                    swaps += 1
                else:
                    break
                j -= 1
        print(f'Comparisons: {comparisons}, Swaps: {swaps}')