QuickSort Returning Recursion Depth Error

Question

I have what should be a simple quicksort implementation, but it's returning a recursion depth exceeded error, and I'm testing it on a list of less than 30 elements. Moreover, my implementation was working on a list of 10,000 a few days ago, and the only thing I changed was moving it from a Class to a global function. Anyone see what may be causing this?

def quickSort(m, left, right):
    if len(m[left:right]) <= 1:
        return m
    pivot = m[left]
    i = left + 1
    j = left + 1
    for j in range(j, right):
        if m[j] <= pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
    m[left], m[i-1] = m[i-1], m[left]
    m = quickSort(m, left, i)
    m = quickSort(m, i, right)
    return m

for j in range(j, right): that can't be good (for readability for the very least) — amit
– amit, Commented Nov 14, 2012 at 17:59
Add some print statements and re-run to see how it progress. — Wai Yip Tung
– Wai Yip Tung, Commented Nov 14, 2012 at 18:23

Christian Thieme · Accepted Answer · 2012-11-14 19:31:22Z

2

one of your recursive calls is causing the exception(as you may have guessed :-), also note that you sort the list in place so returning the list is not necessary

def quickSort(m, left, right):
    if right - left  <= 1:
        return

    pivot = m[left]
    i = left + 1 
    j = left + 1 
    for j in range(j, right):
        if m[j] <= pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
    m[left], m[i-1] = m[i-1], m[left]
    quickSort(m, left, i-1)
    quickSort(m, i, right)

answered Nov 14, 2012 at 19:31

Christian Thieme

1,1246 silver badges6 bronze badges

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

1 Comment

Asiri Rathnayake Over a year ago

Yup, the pivot should be excluded when sorting the sub-list. Good one, I missed it :)

Collectives™ on Stack Overflow

QuickSort Returning Recursion Depth Error

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