I wrote a code about Quick sort and the problem is, I get a Recursion Error for large Arrays with, for Example, over 1000 values. However, I don't have the problem with small Arrays. I don't know why I get the Error. Can someone help me?

My Code:

last = object()
def quicksort(array, start= 0, ende = last):

    if ende is last:
        ende = (len(array) -1)


    def partition(array, anfang, ende):
        piv_index = anfang
        piv = array[piv_index]

        while anfang < ende:
            while anfang < len(array) and array[anfang] <= piv:
                anfang  = 1

            while array[ende] > piv:
                ende -= 1

            if anfang < ende:
                array[anfang], array[ende] = array[ende], array[anfang]

        array[ende], array[piv_index] = array[piv_index], array[ende]

        return ende

    if start < ende:

        p = partition(array, start, ende)

        quicksort(array, start, p-1)
        quicksort(array, p 1, ende)
    return(array)

CodePudding user response：

As mentioned in the comments by Barmar there is a recursion limit in Python which seems to be 1000.

You can see the actual value on your system with the function getrecursionlimit(), which on my system is 1000 (Python 3).

You can set the recursion limit higher if you need with getrecursionlimit(imit).

You say that you run into the recursion error when testing with 1000 numbers. You must be testing a strictly descending ordered list, e.g. 1000, 999, 998, ..., 1 which will hit the limit.

Actually with the recursion limit set to 1000
and such an input list with 999 items
and your program choice of the pivot
you will hit the limit.
With 998 numbers you'll be ok.

Choosing a higher recursion limit may make sense if you know the maximum size of the array. Otherwise you have to consider a possible recursion error.

What you could do apart from choosing another suitable sort algorithm:

• set the recursion limit to suit your needs if possible
• choose a pivot randomly/accordingly (there are several options here)
• rewrite the Quicksort program so that it is iterative (that's more difficult for some, but spares you the recursion depth problem)

The options have their pros and cons of course, so you have to make a compromise (as I hear quite often the saying you have to die one of the deaths).

CodePudding user response：

To avoid stack overflow, stack space can be limited to O(log2(n)) by recursing on smaller partition, and looping for larger partition. Worst case time complexity remains O(n^2). Also the code is a variation of Hoare partition scheme, which needs some clean up. Example code that uses middle element for pivot with partition logic included in the quick sort function.

def qsort(a, lo, hi):           # hoare, post inc, dec
    while(lo < hi):
        p = a[(lo   hi) // 2]   # pivot
        i = lo
        j = hi
        while(i <= j):
            while(a[i] < p):
                i  = 1
            while(a[j] > p):
                j -= 1
            if(i > j):
                break
            a[i],a[j] = a[j],a[i]
            i  = 1
            j -= 1
        # recurse on smaller part, loop on larger part
        if((j - lo) <= (hi - i)):
            qsort(a, lo, j)
            lo = i
        else:
            qsort(a, i, hi)
            hi = j