CODEWITHSUNDEEP
pythonrecursionstack-overflowquicksorterror-code
Phillip Feldman
Phillip Feldman

Reputation: 77

Quicksort in Python on big input; How do I fix error code: Process finished with exit code -1073741571 (0xC00000FD)?

I wrote a recursive quicksort algorithm in Python to sort a list of 10,000 ints. I am testing a worst case (pivot is always the low index, and the list is already sorted, so one of the recursive calls to quicksort is always empty, and the other always decreases by 1). I know that means I have to increase the recursion limit with

sys.setrecursionlimit(10000)

Now I am getting the error code

Process finished with exit code -1073741571 (0xC00000FD)

I read elsewhere that I should use

threading.stack_size()

But, I have no idea how to use this function. I tried passing in different values, and I will either get that the size is not valid, or the same error code. Can somebody please help me with this?

Upvotes: 0

Views: 75

Answers (1)

rcgldr
rcgldr

Reputation: 28828

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

def qsort(a, lo, hi):
    while(lo < hi):
        p = a[(lo + hi) // 2]       # pivot, any a[] except a[hi]
        i = lo - 1
        j = hi + 1
        while(1):                   # Hoare partition
            while(1):               #  while(a[++i] < p)
                i += 1
                if(a[i] >= p):
                    break
            while(1):               #  while(a[--j] < p)
                j -= 1
                if(a[j] <= p):
                    break
            if(i >= j):             #  if indexes met or crossed, break
                break
            a[i],a[j] = a[j],a[i]   #  else swap elements and loop
        if((j - lo) < (hi - j)):    # recurse on smaller partition
            qsort(a, lo, j)         #  loop on larger partition
            lo = j+1
        else:
            qsort(a, j+1, hi)
            hi = j

Upvotes: 1

Related Questions