I built a Quick Sort algorithm with random pivot, but whenever I try to run the program for a list with 60 sublists, each of which varies in size from 1000 to 500000, I get RecursionError: maximum recursion depth exceeded while calling a Python object. I already tried to increase the recursion limit using sys.setrecursionlimit(limit) but it didn't help.

Here's the code:

def QuickSortRandomico(l: list, start: int = 0, end: int = None) -> list:
    if end is None:
        end = len(l) - 1
    if start < end:
        rand_pivot = randint(start, end)
        l[end], l[rand_pivot] = l[rand_pivot], l[end]
        pivot = start - 1
        for i in range(start, end):
            if l[i] < l[end]:
                pivot = pivot   1
                l[pivot], l[i] = l[i], l[pivot]
        l[pivot   1], l[end] = l[end], l[pivot   1]
        pivot  = 1
        QuickSortRandomico(l, start, pivot - 1)
        QuickSortRandomico(l, pivot   1, end)

CodePudding user response：

Does it need to be recursive? Recursion might burn up too much of your stack. Try this awesome iterative solution by Darel Rex Finley at: Optimized QuickSort — C Implementation (Non-Recursive) which I've converted to Python.

##  quickSort
##
##  This public-domain C implementation by Darel Rex Finley. (Converted to Python...)
##
##  * This function assumes it is called with valid parameters.
##
##  * Example calls:
##    quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4
##    quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7
def quickSort(arr: list, elements: int):
    MAX_LEVELS = 300
    
    piv,L,R,swap = -1,-1,-1,-1
    beg = [None] * MAX_LEVELS
    end = [None] * MAX_LEVELS
    i=0
  
    beg[0]=0
    end[0]=elements
  
    while (i>=0):
        
        L=beg[i] 
        R=end[i]-1
    
        if (L<R):
            piv=arr[L]
            
            while (L<R):
                while (arr[R]>=piv and L<R):
                    R -= 1
                if (L<R): 
                    arr[L]=arr[R]
                    L  = 1
                while (arr[L]<=piv and L<R): 
                    L  = 1
                if (L<R):
                    arr[R]=arr[L]
                    R -= 1
                    
            arr[L]=piv
            beg[i 1]=L 1
            end[i 1]=end[i]
            end[i]=L
            i  = 1
      
            if (end[i]-beg[i]>end[i-1]-beg[i-1]):
                swap=beg[i]
                beg[i]=beg[i-1]
                beg[i-1]=swap
                swap=end[i]
                end[i]=end[i-1]
                end[i-1]=swap 
        
        else:
            i -= 1
    
    return arr
    
for l in ([8,1,2,5], [8,2,1,5], [8,5,2,1], [7,2,9,1,34,2,5,23,11,12,10]):
    print(quickSort(l,len(l)))    

CodePudding user response：

Stack space can be limited to O(log(n)) by recursing on smaller partition, looping on larger. Worst case time complexity still remains O(n^2).

    while start < end:                       # loop
        rand_pivot = randint(start, end)
        l[end], l[rand_pivot] = l[rand_pivot], l[end]
        pivot = start - 1
        for i in range(start, end):
            if l[i] < l[end]:
                pivot = pivot   1
                l[pivot], l[i] = l[i], l[pivot]
        l[pivot   1], l[end] = l[end], l[pivot   1]
        pivot  = 1
        if (pivot-start) <= (end - pivot):   #recurse on smaller, loop on larger
            QuickSortRandomico(l, start, pivot - 1)
            start = pivot 1
        else:
            QuickSortRandomico(l, pivot   1, end)
            end = pivot-1