python - 在 Python 中计算 QuickSort 中的交换次数

Question

我试图在不使用全局变量的情况下计算快速排序中进行的交换次数。我在 Python帖子中尝试了类似的快速排序比较计数器，但没有得到正确的交换次数。我的代码在下面，测试用例返回 1，但它应该返回 3。关于如何更改它以获得正确的交换计数的任何见解？

编辑：问题出在我的算法上，而不是交换计数器。我更新了代码以返回 i 而不是 j，并将 j 递增到最后。掉期的数量显着增加，但我认为它是准确的？

def _partition(input_list, begin, end):
    # For counting the number of swaps
    count = 0
    # Picks the last number in the list as the pivot
    pivot = input_list[end]

    i = begin
    j = begin
    while j < end:
        if input_list[j] < pivot:
            count += 1
            input_list[i], input_list[j] = input_list[j], input_list[i]
            i += 1
        j += 1

    count += 1
    input_list[i], input_list[end] = input_list[end], input_list[i]
    return i, count


def _quickSort(input_list, begin, end):
    count = 0
    if begin < end:
        pivot, count = _partition(input_list, begin, end)
        count += _quickSort(input_list, begin, pivot-1)
        count += _quickSort(input_list, pivot + 1, end)
    return count


def quickSort(input_list, begin=None, end=None):
    if begin == None:
        begin = 0
    if end == None:
        end = len(input_list) - 1
    return _quickSort(input_list, begin, end)


test = [1, 3, 5, 2, 4, 6, 7]
counter = quickSort(test)
print(counter)
print(test)

test2 = [3, 7, 6, 9, 1, 8, 10, 4, 2, 5]
counter1 = quickSort(test2)
print(counter1)
print(test2)

标签： pythonquicksort