Getting maximum recursion depth error when running quicksort algorithms one after another, but not individually

Question

I have to run various versions of the quicksort, counting sort and bubble sort algorithms on a bunch of data files containing unsorted numbers to log the time the algorithm takes on different data sets, and I want to do a script so I don't have to manually run them for each file (I have a lot).

When I run the various algorithms by themselves, calling them manually in the console with Python "algorithmname".py -f "testfilepath", everything works fine. Unfortunately, when I run my script to run them one after each other on each test files, I am having problems with the 4 quicksort versions I have implemented. Each and everytime I run my script to run the algorithms one after another, I get the following error: RuntimeError: Maximum recursion depth exceeded in comparison.

Here is how I call the algorithms one after another in my script file:

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)

In the main function of the quicksort algorithms, I just call the quick() function, which is the function that implements the quicksort algorithm, with the good parameters. Here is an example:

def main(unsortedList):
    # Execute algorithm
    start = time.clock()
    sortedList = quick(unsortedList, 0, (len(unsortedList) - 1), mediane=True, seuilRecurcivite=1)
    end = time.clock()

    return (end - start, sortedList)

And here is my quicksort implementation:

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

medianIndex() is just a function that will find the index of the median number between the first, middle and last element of the list.

The console tells me that the error happens for the line

for i in range(left, right):

but I can't find out why it gives me that error when I run the script that just runs every algorithms one after another but not when I run the separately.

Thanks for your help.

EDIT: As demanded, here is the medianIndex() function and the med3() function it internally uses:

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

So i have found my problem. It is in the following code:

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

The correct way to do that would be to do the following:

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 = list(unsortedList1)
    unsortedList3 = list(unsortedList1)
    unsortedList4 = list(unsortedList1)
    unsortedList5 = list(unsortedList1)
    unsortedList6 = list(unsortedList1)

as to create a new list based on unsortedList1, and not just point to unsortedList1. This solved partly my issue.

Another problem I had afterwards was still getting the same error, but only on the biggest data sets (100 000 or 500 000 numbers). This problem was solved by using sys.setrecursionlimit