Modified quicksort exceeded maximum recursion depth

Question

I try to recreate modified quicksort from here https://link.springer.com/chapter/10.1007/978-981-15-6648-6_26#enumeration

the code give this error RecursionError: maximum recursion depth exceeded in comparison when array length > 9

here is my code

def quick_sort(arr,low,high):
    n = high-low+1
    if n<=3:
        manual_sort(arr,low,high)
    else:
        a = calculate_pivot(arr,low,high)
        q = partition(arr,low,high,a)
        quick_sort(arr,low,q)
        quick_sort(arr,q+1,high)

def calculate_pivot(arr,low,high):
    temp_arr = arr[low:high+1]
    #print(temp_arr)
    left_arr = temp_arr[:len(temp_arr)//2]
    right_arr = temp_arr[len(temp_arr)//2:]
    avg_left = (max(left_arr)+min(left_arr))/len(left_arr)
    avg_right = (max(right_arr)+min(right_arr))/len(right_arr)
    return (avg_left+avg_right)/2

def manual_sort(arr,low,high):
    n = high-low+1
    if n<=1:
        return
    if n==2:
        if arr[low]>arr[high]:
            arr[low] = arr[low] + arr[high]
            arr[high] = arr[low] - arr[high]
            arr[low] = arr[low] - arr[high]
    if n==3:
        if arr[low]>arr[high-1]:
            arr[low] = arr[low] + arr[high-1]
            arr[high-1] = arr[low] - arr[high-1]
            arr[low] = arr[low] - arr[high-1]
    if arr[low]>arr[high]:
        arr[low] = arr[low] + arr[high]
        arr[high] = arr[low] - arr[high]
        arr[low] = arr[low] - arr[high]
    if arr[high-1]>arr[high]:
        arr[high-1] = arr[high-1] + arr[high]
        arr[high] = arr[high-1] - arr[high]
        arr[high-1] = arr[high-1] - arr[high]

def partition(arr,low,high,pivot):
    i = low-1
    j = high+1
    while 1:
        i+=1
        while arr[i]<pivot:
            i+=1
        j-=1
        while arr[j]>pivot:
            j-=1
        if i>=j:
            return j
        arr[i],arr[j] = arr[j],arr[i]

i notice this paper use some kind of hoare partition scheme so I try to compare with this https://www.geeksforgeeks.org/quick-sort/ but i still can't find what's wrong

Assuming your partition is correct, you can limit recursion depth to O(log n) by only recurring on the smaller partition. See the first bullet point here. — Blastfurnace
@Blastfurnace good information, but I think here is a case where they are entering infinite recursion. — juanpa.arrivillaga

rcgldr rcgldr · Accepted Answer · 2021-01-03T21:46:24

For Hoare partition scheme, the pivot value must be an actual value in the sub-array being partitioned, not an average. In this code, I used the middle value for pivot. With this particular implementation of partition, any value other than arr[high] can be used for the pivot. Using arr[high] with this implementation will typically lead to infinite recursion or looping in the second code example (because partition will return q == high). I also fixed some other bits in this code:

def quick_sort(arr,low,high):
    n = high-low+1
    if n<=3:
        manual_sort(arr,low,high)
    else:
        a = calculate_pivot(arr,low,high)
        q = partition(arr,low,high,a)
        quick_sort(arr,low,q)
        quick_sort(arr,q+1,high)

def calculate_pivot(arr,low,high):
    return arr[(low+high)//2]

def manual_sort(arr,low,high):
    n = high-low+1
    if n<=1:
        return
    if n==2:
        if arr[low]>arr[high]:
            arr[low] = arr[low] + arr[high]
            arr[high] = arr[low] - arr[high]
            arr[low] = arr[low] - arr[high]
    if n==3:
        if arr[low]>arr[high-1]:
            arr[low] = arr[low] + arr[high-1]
            arr[high-1] = arr[low] - arr[high-1]
            arr[low] = arr[low] - arr[high-1]
        if arr[low]>arr[high]:
            arr[low] = arr[low] + arr[high]
            arr[high] = arr[low] - arr[high]
            arr[low] = arr[low] - arr[high]
        if arr[high-1]>arr[high]:
            arr[high-1] = arr[high-1] + arr[high]
            arr[high] = arr[high-1] - arr[high]
            arr[high-1] = arr[high-1] - arr[high]

def partition(arr,low,high,pivot):
    i = low-1
    j = high+1
    while 1:
        while 1:
            i+=1
            if(arr[i]>=pivot):
                break
        while 1:
            j-=1
            if(arr[j]<=pivot):
                break
        if i>=j:
            return j
        arr[i],arr[j] = arr[j],arr[i]

To prevent stack overflow, recurse on the smaller partition, loop back for the larger partition. This limits stack complexity to O(log(n)), but worst case time complexity remains at O(n^2).

def quick_sort(arr,low,high):
    while((high-low) >= 3):
        a = calculate_pivot(arr,low,high)
        q = partition(arr,low,high,a)
        if((q+1-low) <= (high-q)):
            quick_sort(arr,low,q)
            low = q+1
        else:
            quick_sort(arr,q+1,high)
            high = q
    manual_sort(arr,low,high)

Modified quicksort exceeded maximum recursion depth

1 Answers