My quicksort in Python3 is breaking the recursion limit

1
from random import *
from time import *
import sys


def quicksort(mylist, pivot, end):
    # pivot will always be the first element in the list/sub-list
    if (len(mylist) == end) and (pivot == 0):  # shuffle the list before we start (only happens on the first call)
        shuffle(mylist)
    if (pivot == end) or (pivot == end-1):
        return mylist
    sr = pivot + 1  # start from element after pivot
    sl = end - 1  # start from end of list
    smaller = None
    bigger = None
    smallest_index = 0

    while sr <= sl:
        if mylist[sr] > mylist[pivot]:
            bigger = mylist[sr]
        else:
            sr += 1
        if mylist[sl] < mylist[pivot]:
            smaller = mylist[sl]
        else:
            sl -= 1
        if (sr < sl) and (smaller is not None) and (bigger is not None):
            mylist[sr] = smaller
            mylist[sl] = bigger
            smallest_index = sr
            sr += 1
            sl -= 1
            smaller = None
            bigger = None
        if (sr-1 == sl) and ((smaller is not None) or (mylist[sl] <= mylist[pivot])):
            smaller = mylist[sl]
            smallest_index = sl

    mylist[smallest_index], mylist[pivot] = mylist[pivot], mylist[smallest_index]
    quicksort(mylist, pivot, smallest_index)
    quicksort(mylist, smallest_index+1, end)
    return mylist

I also used sys.setrecursionlimit(1000000) because it was originally breaking the limit with larger lists, but I end up getting exit code 0xC00000FD

I've been working at this for hours and just can't seem to crack it. I can't tell if I just need a better implementation or if I went wrong somewhere. This was the only implementation I could come up with unfortunately.

Help please?

python
python-3.x
recursion
quicksort
asked on Stack Overflow Feb 13, 2020 by zekrofire

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0