Quicksort algorithm with python raises RecursionError

Question

I've been trying to debug my code for some hours and haven't had a headway with it. I love if anyone could help me, I just started learning algorithms

def quicksort(arr):
    start = 0
    end = len(arr) - 1
    quick_sort(arr, start, end)


def quick_sort(arr, start, end):
    if start < end:
        pindex = partition(arr, start, end)
        quick_sort(arr, start, pindex)
        quick_sort(arr, pindex+1, end)


def partition(arr, start, end):
    pivot = arr[end]
    i = start
    for j in range(start, end):
        if arr[j]<= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[end] = pivot, arr[i]
    return i;

when i run it with quicksort([6,4,5,4,2,43,1,4,532,515,243,3,34,5,12,24,234,45,6,457,5])

I get

RecursionError: maximum recursion depth exceeded in comparison

and I'm quite sure I used a base case at the beginning of the quick_sort function

Actually, you did not "show ... the full traceback for any errors." It would also be best to include your call to your function, with its input, in your code. — Rory Daulton
– Rory Daulton, Commented Aug 4, 2018 at 9:41
You can try to increase recursion depth using sys.getrecursionlimit. But do it carefully. — Lev Zakharov
– Lev Zakharov, Commented Aug 4, 2018 at 9:44

Rory Daulton · Accepted Answer · 2018-08-04 09:48:01Z

3

Your quicksort and quick_sort routine use, as parameters, the index of the first and of the last item in the sub-array to be sorted. After you partition the sub-array, you sort two parts. However, you include the pivot element of the partition in the first part in your call quick_sort(arr, start, pindex). You should leave the pivot element out, so use quick_sort(arr, start, pindex-1).

Give that a try. You have no comments so it is difficult to debug your program. Your example input is also far too large and difficult to debug easily. Try an empty array, then an array with one element, then some arrays with two elements, and so on, to catch your errors.

With that one change, your program now passes all my tests.

answered Aug 4, 2018 at 9:48

Rory Daulton

22.7k7 gold badges46 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

TOLULOPE ADETULA Over a year ago

Thanks a lot. It was really helpful

Collectives™ on Stack Overflow

Quicksort algorithm with python raises RecursionError

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related