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?
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