pythonalgorithmsortinginsertion-sort

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


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?


Solution

  • 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