How can I get the correct count of comparisons made in insertion sort?

Question

I am trying to complete an activity that goes through an insertion sort and counts the number of comparisons made. Everything is right except for the comparison count. For some reason I cannot get the correct number of comparisons. Here is the code that I have so far:

comparisons = 0
swaps = 0


def read_nums():
    """Read numbers from input and return them in a list"""
    return [int(num) for num in input().split()]


def print_nums(nums):
    """Output numbers, separating each item by spaces;
    no space or newline before the first number or after the last."""
    print(' '.join([str(n) for n in nums]), end='')


def swap(nums, n, m):
    """Exchange nums[n] and nums[m]"""
    nums[n], nums[m] = nums[m], nums[n]


def insertion_sort(numbers):
    """Sort the list numbers using insertion sort"""
    global comparisons
    global swaps

    for i in range(1, len(numbers)):
        j = i
        # Insert numbers[i] into the sorted part
        # stopping once numbers[i] is in the correct position
        while j > 0 and numbers[j] < numbers[j - 1]:
            comparisons += 1
            swap(numbers, j, j - 1)
            swaps += 1
            j -= 1

        comparisons += 1



        # Output the list during each iteration of the outside loop
        print_nums(numbers)
        print()  # Add a newline after each iteration


if __name__ == '__main__':
    # Step 1: Read numbers into a list
    numbers = read_nums()

    # Step 2: Output the numbers list
    print_nums(numbers)
    print(end='\n\n')

    # Step 3: Sort the numbers list
    insertion_sort(numbers)
    print()

    # Step 4: Output the number of comparisons and swaps performed
    print(f"comparisons: {comparisons}")
    print(f"swaps: {swaps}")

I tried incrementing comparisons inside, outside and both inside and outside of the while loop but none of those routes takes me to the correct number of comparisons. The tests fail no matter where I increment comparisons variable.

With an input of "3 2 1 5 9 8" the number of comparisons should be 7 but I am getting 9. What am I doing wrong?

Answer 1

Your implementation is broken as you do not break the loop when number[j] is in good position. The loop can be rewritten as in the following with an appropriate counting:

    while j > 0:
        comparisons += 1  # there will be a comparison just after, whatever will be its result
        if numbers[j] < numbers[j - 1]:
            swap(numbers, j, j - 1)
            swaps += 1
        else:             # break the loop as the right position was found
            break
        j -= 1

A run will produce:

comparisons: 7
swaps: 4

And for input 1 2 3 4:

comparisons: 4
swaps: 0

Answer 2

I suppose, you are working on a program that uses the insertion sort algorithm to sort a list of numbers while keeping track of the number of comparisons made. Everything seems to be in order, but you're having trouble accurately counting the comparisons.

The issue lies in how you're counting comparisons. Right now, you're counting both successful and unsuccessful comparisons, which is why the count isn't correct.

To count only the successful comparisons (those that lead to an actual swap), you should make a small change in your code. Move the line that increments the comparisons variable inside the if condition that checks if a swap is needed.

By doing this, you'll accurately count only the comparisons that result in swaps, which is the standard way to count comparisons in sorting algorithms. This should give you the correct number of comparisons made during the insertion sort.

def insertion_sort(numbers):
global comparisons
global swaps

for i in range(1, len(numbers)):
    j = i
    # Insert numbers[i] into the sorted part
    # stopping once numbers[i] is in the correct position
    while j > 0 and numbers[j] < numbers[j - 1]:
        swap(numbers, j, j - 1)
        swaps += 1
        comparisons += 1  # Count a comparison only when a swap is made
        j -= 1

    # Output the list during each iteration of the outside loop
    print_nums(numbers)
    print()  # Add a newline after each iteration

Answer 3

The issue with your code is that you are counting comparisons both inside and outside the while loop, which results in double-counting some comparisons. To correct the count, you should only increment the comparisons variable inside the while loop when a comparison is made.

def insertion_sort(numbers):
"""Sort the list numbers using insertion sort"""
global comparisons
global swaps

for i in range(1, len(numbers)):
    j = i
    # Insert numbers[i] into the sorted part
    # stopping once numbers[i] is in the correct position
    while j > 0 and numbers[j] < numbers[j - 1]:
        swap(numbers, j, j - 1)
        swaps += 1
        j -= 1
        comparisons += 1  # Increment comparisons for each comparison, not just swaps

Answer 4

Your code also counts as comparison when j > 0 is evaluated and found to be False. In that case the second expression in the while condition is not evaluated (short-circuit evaluation), and this "comparison" of j alone does not count. In the context of evaluating sort algorithms, the number of comparisons refers only to comparisons that involve values in the input list, not indices. When j happens to be 0 there will be no comparison made that involves numbers[j].

So to achieve a correct comparison count, check whether the loop was exited because of j being 0 (in which case the count should not be incremented), or because of the data comparison (in which we do need to increment the count):

def insertion_sort(numbers):
    """Sort the list numbers using insertion sort"""
    global comparisons
    global swaps
    
    for i in range(1, len(numbers)):
        j = i
        # Insert numbers[i] into the sorted part
        # stopping once numbers[i] is in the correct position
        while j > 0 and numbers[j] < numbers[j - 1]:
            comparisons += 1
            swap(numbers, j, j - 1)
            swaps += 1
            j -= 1
        if j > 0:  # ...then we had evaluated the second expression in while condition
            comparisons += 1