Lomuto分区快速排序添加计数功能后触发RecursionError求助

问题场景 #

基于Lomuto分区实现的快速排序添加交换、比较次数统计功能后，触发RecursionError，预期输出统计结果(15,9)，原实现代码如下：

def partition(arr, low, high):
    
    # pivot
    pivot = arr[high]
    comp = 0
    swap = 0
    
    # Index of smaller element
    i = (low - 1)
    for j in range(low, high):
        comp+=1
        # If current element is smaller than or
        # equal to pivot
        if (arr[j] <= pivot):
            # increment index of smaller element
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            swap+=1
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    swap+=1
    return (comp, swap, i + 1)

def quicksort(A, lo, hi):
  if lo >= 0 and hi >= 0 and lo < hi:
    (comp, swap, p) = partition(A, lo, hi)
    # get the number of comps and swaps on the left and right sides
    (lcomp, lswap) = quicksort(A, lo, p)
    (rcomp, rswap) = quicksort(A, p + 1, hi)
    # return the combined total of comps and swaps
    return (comp + lcomp + rcomp, swap + lswap + rswap)
    # base case
  return (0,0)
        
''' Function to print an array '''
def printArray(arr, size):
    
    for i in range(size):
        print(arr[i], end = " ")
    print()

# Driver code

arr = [2,8,7,1,3,5,6,4]
n = len(arr)
quicksort(arr, 0, n - 1)
print("Sorted array:")
printArray(arr, n)

错误原因分析 #

递归边界处理错误导致无限递归：

• Lomuto分区完成后，p是pivot元素最终的排序位置，该位置的元素已处于正确位置，无需再参与后续递归。
• 原代码中左侧递归调用为quicksort(A, lo, p)，当子数组缩小到仅剩单个元素时，会出现lo = p-1的情况，此时quicksort(A, lo, p)的入参满足lo < hi条件，会重复执行分区操作，而分区后得到的p位置不变，导致递归无法终止，最终触发RecursionError。

修复方案 #

将左侧递归的右边界改为p-1，确保已排序的pivot元素不再被重复处理，修正后的quicksort函数如下：

def quicksort(A, lo, hi):
  if lo >= 0 and hi >= 0 and lo < hi:
    (comp, swap, p) = partition(A, lo, hi)
    # 修正左侧递归的右边界为p-1
    (lcomp, lswap) = quicksort(A, lo, p - 1)
    (rcomp, rswap) = quicksort(A, p + 1, hi)
    return (comp + lcomp + rcomp, swap + lswap + rswap)
  return (0,0)

验证结果 #

修正后运行代码，会返回预期的统计结果(15,9)，同时数组能正常完成排序。

内容的提问来源于stack exchange，提问作者William Moore