python - 通过 Python 计算快速排序期间对列表的总访问量

问题描述

我的任务是通过 Python 计算快速排序程序中的列表访问总数。请检查以下代码：

arr1 = [4, 5, 3, 7, 2]
def inplace_quick_sort(arr, a, b, y):
    count = y
    count += 1  # for the access to the "a" element in the list while calling the function
    if a >= b:
        return

    count += 1  # access for arr[b]
    pivot = arr[b]
    left = a
    right = b - 1
    while left <= right:

        count += 1  # access for arr[left]
        while left <= right and arr[left] <= pivot:
            left += 1

        count += 1  # access for arr[right]
        while left <= right and pivot < arr[right]:
            right -= 1

        if left <= right:
            count += 4  # access for swap left and right
            arr[left], arr[right] = arr[right], arr[left]
            left, right = left + 1, right - 1

    count += 4  # access for swap left and last
    print(count)
    arr[left], arr[b] = arr[b], arr[left]
    inplace_quick_sort(arr, a, left - 1, count)
    inplace_quick_sort(arr, left + 1, b, count)

x = 0
print("count = " + str(inplace_quick_sort(arr1, 0, len(arr1) - 1, x)))

我有两个问题。第一个是“计数”正确添加列表访问的数字？第二个是我得到如下有线输出：

count = 8

我不明白关于“计数”的迭代。为什么“计数”等于 8？“计数”假设大于 8。抱歉，我在代码中犯了一些错误。我修改了它，仍然得到有线输出。我很感激你的任何指导。非常感谢。

标签： pythoncountiterationquicksort

正确计算数组访问次数所需的主要更改是：

保留count为全局变量，以便inplace_quick_sort()函数末尾的每个分支都更新相同的计数器。y从函数定义和用法中删除，并以global count.
count += 1之前的两个while应该就在每个循环的内部/开始处，while因为每个 while 循环都在访问arr[left]或arr[right]。因此，该计数器应在每次迭代时递增while
对于 statements while left <= right and arr[left] <= pivot，没有必要arr[left]访问 - 如果left <= right为 False，则arr[left] <= pivot永远不会评估，arr[left]也不会访问。这必须分成不同的步骤：
该行应该被删除，因为a当你调用它时它只会被访问一次。剩下的时间，它是递归的，所以更新count 那里。
- count += 1 # for the access to the "a" element in the list while calling the function
如果数组“访问”只包括读取而不包括写入，那么这两count += 4行应该是 just count += 2。我已按照您的代码保留它，相应地对其进行更改或保持原样。

def inplace_quick_sort(arr, a, b):
    global count
    if a >= b:
        return

    count += 1  # access for arr[b]
    pivot = arr[b]
    left = a
    right = b - 1
    while left <= right:

        while left <= right:
            count += 1  # access for arr[left]
            if arr[left] <= pivot:
                left += 1
            else:
                break  # needed to match the original while-logic

        while left <= right:
            count += 1  # access for arr[right]
            if pivot < arr[right]:
                right -= 1
            else:
                break  # needed to match the original while-logic

        if left <= right:
            count += 4  # access for swap left and right
            arr[left], arr[right] = arr[right], arr[left]
            left, right = left + 1, right - 1

    count += 4  # access for swap left and last
    # print(count)
    arr[left], arr[b] = arr[b], arr[left]
    inplace_quick_sort(arr, a, left - 1)
    inplace_quick_sort(arr, left + 1, b)

执行：

arr1 = [4, 5, 3, 7, 2]
count = 1  # because you sart with `len(arr1)`
inplace_quick_sort(arr1, 0, len(arr1) - 1)
print("count = ", count)
print('array afer:', arr1)

输出：

count =  30
array afer: [2, 3, 4, 5, 7]

顺便说一句，如果您确实想count用作局部变量，那么：

应用上述更改，但跳过 #1。
if a >= b: return声明应该是if a >= b: return count

每次调用都inplace_quick_sort应该增加前一个count，并确保return count在最后：

count = inplace_quick_sort(arr, a, left - 1, count)
count = inplace_quick_sort(arr, left + 1, b, count)
return count

此外，这个答案只是count正确的，而不是修复快速排序的实现。

python - 通过 Python 计算快速排序期间对列表的总访问量

问题描述

解决方案

推荐阅读