当一个接一个地运行快速排序算法，而不是单独运行时，获取最大递归深度错误

Question

我必须运行各种版本的快速排序，在一堆包含未排序数字的数据文件上计算排序和气泡排序算法，以记录算法处理不同数据集的时间，我想编写一个脚本，这样就不必为每个文件手动运行它们（我有很多）。在

当我自己运行各种算法，在控制台中用Python“algorithmname”.py-f“testfilepath”手动调用它们时，一切正常。不幸的是，当我运行脚本在每个测试文件上逐个运行它们时，我对我实现的4个快速排序版本有问题。每次我运行我的脚本来运行一个又一个的算法时，我都会得到以下错误：RuntimeError:Maximum recursion depth exceeded in comparison。在

下面是我如何在脚本文件中逐个调用算法：

for dataFile in sorted(listdir("tp1-H10-donnees")):
    inputFile = open("tp1-H10-donnees/" + dataFile, "r")    
    unsortedList1 = [int(line.rstrip('\n')) for line in inputFile]
    unsortedList2 = unsortedList1
    unsortedList3 = unsortedList1
    unsortedList4 = unsortedList1
    unsortedList5 = unsortedList1
    unsortedList6 = unsortedList1

    (algoTime, sortedList) = bubble.main(unsortedList1)
    bubbleResult.append(dataFile + "\tbubble sort\t" + ", time = %.6f\n" % algoTime)

    (algoTime, sortedList) = counting.main(unsortedList2)
    countingResult.append(dataFile + "\tcounting sort\ttime = %.6f\n" % algoTime)

    (algoTime, sortedList) = quick.main(unsortedList3)
    quickResult.append(dataFile + "\tquick sort\ttime = %.6f\n" % algoTime)

    (algoTime, sortedList) = quickMed.main(unsortedList4)
    quickMedResult.append(dataFile + "\tquickMed sort\ttime = %.6f\n" % algoTime)

    (algoTime, sortedList) = quickSeuil.main(unsortedList5)
    quickSeuilResult.append(dataFile + "\tquickSeuil sort\ttime = %.6f\n" % algoTime)

    (algoTime, sortedList) = quickMedSeuil.main(unsortedList6)
    quickMedSeuilResult.append(dataFile + "\tquickMedSeuil sort\ttime = %.6f\n" % algoTime)

在快速排序算法的主函数中，我只调用quick（）函数，它是实现快速排序算法的函数，具有良好的参数。下面是一个例子：

^{pr2}$

下面是我的快速排序实现：

import math

def quick(unsortedList, left, right, mediane=False, seuilRecurcivite=1):

    if right - left >= seuilRecurcivite:
        if (mediane == False):
            pivotIndex = left
        else:
            pivotIndex = medianIndex(unsortedList, left, right);
        pivotNewIndex = partition(unsortedList, left, right, pivotIndex)
        quick(unsortedList, left, pivotNewIndex - 1)
        quick(unsortedList, pivotNewIndex + 1, right)
    elif right - left >= 1:
        unsortedList[left:right+1] = bubble(unsortedList[left:right+1])

    return unsortedList

def partition(unsortedList, left, right, pivotIndex):
    pivotValue = unsortedList[pivotIndex]
    unsortedList[pivotIndex], unsortedList[right] = unsortedList[right], unsortedList[pivotIndex]
    storeIndex = left

    for i in range(left, right):    # RUNTIME ERROR
        if unsortedList[i] <= pivotValue:
            unsortedList[i], unsortedList[storeIndex] = unsortedList[storeIndex], unsortedList[i]
            storeIndex = storeIndex + 1

    unsortedList[storeIndex], unsortedList[right] = unsortedList[right], unsortedList[storeIndex]

    return storeIndex

mediaIndex（）只是一个函数，它将查找列表的第一个、中间和最后一个元素之间的中位数的索引。在

控制台告诉我该行发生了错误

for i in range(left, right):

但是我不明白为什么当我运行一个接一个地运行每一个算法的脚本时，为什么它会给我这个错误，但是当我单独运行时却没有。在

谢谢你的帮助。在

编辑： 根据需要，这里是medianIndex（）函数及其内部使用的med3（）函数：

def med3(a, b, c):
    if a <= b <= c or c <= b <= a:
        return b
    elif b <= a <= c or c <= a <= b:
        return a
    else:
        return c

def medianIndex(list, left, right):
    firstValue = list[left]
    lastValue = list[right]
    middleValue = list[math.ceil((left + right) / 2)]

    medianValue = med3(firstValue, middleValue, lastValue)

    return list.index(medianValue)

Answer 1

所以我发现了我的问题。它在以下代码中：

for dataFile in sorted(listdir("tp1-H10-donnees")):
    inputFile = open("tp1-H10-donnees/" + dataFile, "r")    
    unsortedList1 = [int(line.rstrip('\n')) for line in inputFile]
    unsortedList2 = unsortedList1
    unsortedList3 = unsortedList1
    unsortedList4 = unsortedList1
    unsortedList5 = unsortedList1
    unsortedList6 = unsortedList1

正确的方法是执行以下操作：

^{pr2}$

创建一个基于unsortedList1的新列表，而不仅仅是指向unsortedList1。这部分解决了我的问题。在

我后来遇到的另一个问题仍然是同样的错误，但只在最大的数据集（10万或50万个数字）上。这个问题通过使用sys.setrecursionlimit来解决