如何获得插入排序中正确的比较次数？

Question

我正在尝试完成一项通过插入排序并计算比较次数的活动。除了比较计数之外，一切都正确。由于某种原因，我无法获得正确的比较次数。这是我到目前为止的代码：

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}")

我尝试增加 while 循环内部、外部以及内部和外部的比较，但这些路线都没有让我达到正确的比较次数。无论我在哪里增加比较变量，测试都会失败。

输入“3 2 1 5 9 8”，比较次数应该是 7，但我得到 9。我做错了什么？

Answer 1

我想，您正在开发一个程序，该程序使用插入排序算法对数字列表进行排序，同时跟踪进行的比较次数。一切似乎都井然有序，但您在准确计算比较时遇到了困难。

问题在于你如何计算比较。现在，您正在计算成功和不成功的比较，这就是计数不正确的原因。

要仅计算成功的比较（导致实际交换的比较），您应该对代码进行一些小更改。将增加比较变量的行移到检查是否需要交换的 if 条件内。

通过这样做，您将仅准确地计算导致交换的比较，这是在排序算法中计算比较的标准方法。这应该为您提供插入排序期间进行的正确比较次数。

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