通过 Python 计算快速排序期间对列表的总访问次数

Question

我的作业是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。抱歉，我在代码中犯了一些错误。我修改了它，仍然得到有线输出。感谢您的任何指导。非常感谢。

Answer 1

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

将 count 保留为全局变量，以便 inplace_quick_sort() 的每个分支在函数末尾更新相同的计数器.从函数定义和用法中删除 y 并使用 global count.
启动主函数
while 之前的两个 count += 1 应该只是 inside/at 每个 while 循环的开始，因为每个 while 循环都在访问arr[left] 或 arr[right]。因此，该计数器应在 while
的每次迭代中递增
对于语句 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
如果数组“access”只包含读不写，那么count += 4两行应该就是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 计算快速排序期间对列表的总访问次数

Counting total access to the list during the quicksort by Python

python

iteration

count

quicksort