Quicksort Partition Python

Question

I am having some trouble with my quicksort. Here is my program:

def main():
     Array = [10, 5, 3, 8, 6, 7, 4, 9, 2, 1, 10]
     right_index = (len(Array) - 1)
     left_index = 0
     Quicksort(Array, left_index, right_index)

def Quicksort(Array, left_index, right_index):
    if len(Array) == 1:
        return Array
    pivot_index = Partition(Array, left_index, right_index)
    Quicksort(Array, left_index, pivot_index-1)
    Quicksort(Array, pivot_index + 1, right_index)
    return Array

def Partition(Array, left_index, right_index):
    pivot = Array[left_index]
    i = left_index + 1
    for j in range(left_index + 1, right_index):
        if Array[j] <= pivot:
            Array[j], Array[i] = Array[i], Array[j]
            i += 1
    Array[left_index], Array[i - 1] = Array[i - 1], Array[left_index]
    return i - 1

main()

Am I doing something wrong? I get the error: for j in range(left_index + 1, right_index):

RecursionError: maximum recursion depth exceeded in comparison".

Thanks for any assistance anyone out there may have.

I added a statement before calling partition, to make sure left_index was always less than right index so it didn't recursively call forever, is that correct? Though now I'm getting the error: Array[left_index], Array[i-1] = Array[i-1], Array[left_index] IndexError: list index out of range — Noah Hoefle
– Noah Hoefle, Commented Apr 4, 2018 at 5:49
buddy you're missing th point that len(Array) will never reduce in the way you're calling function. — moghya
– moghya, Commented Apr 4, 2018 at 5:54
Could you be a little more elaborate? I apprecate your help, I'm sorry and relatively new to recursive algorithms. — Noah Hoefle
– Noah Hoefle, Commented Apr 4, 2018 at 6:27

M Oehm · Accepted Answer · 2018-04-04 06:51:39Z

1

When you get a recursion error, there's usually something wrong with your termination condition. (That's what moghya was trying to tell you, albeit not very clearly.) In your case:

if len(Array) == 1:
    return Array

You use two indices to keep track of which subarray you are currently treating. The base array Array will always have a length of 11; the only changes you make to that array is to swap elements around. Therefore, your termination condition should be:

if left_index >= right_index:
    return Array

There is another mistake in your code: When you partition your array, you miss out on the last element. Here:

for j in range(left_index + 1, right_index):

the upper bound should be right_index + 1. This off-by one error was probably introduced because you chose to use an inclusive upper bound, that is right_index is the last valid index.

This is not how Python (and many other languages) handle arrays. Python arrays and ranges have an inclusive lower bound and an exclusive upper bound. Zero-based indices and exclusive upper bound seem a bit conterintuitive at first, but I suggest that you embrace rather than fight this convention.

I also suggest that you write a wrapper quicksort function that doesn't require passing in the array bound explicitly. Putting all this together, you get:

def main():
     Array = [10, 5, 3, 8, 6, 7, 4, 9, 2, 1, 10]
     quicksort(Array)

     print Array

def quicksort(a):
    quicksort_sort(a, 0, len(a))
    return a

def quicksort_sort(a, left, right):
    if left + 1 < right:
        ipivot = quicksort_part(a, left, right)    
        quicksort_sort(a, left, ipivot)
        quicksort_sort(a, ipivot + 1, right)

def quicksort_part(a, left, right):
    pivot = a[left]
    i = left + 1

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

    a -= 1
    a[left], a[i] = a[i], a[left] 

    return i

main()

answered Apr 4, 2018 at 6:51

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

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

2 Comments

Noah Hoefle Over a year ago

Very informative thank you, heading to sleep and reading this on my phone but I’m pretty sure that cleared up my confusions, cheers

SgtPepper Over a year ago

I'd suggest editing your code since you have a type error when you try to decrease the array by 1, I believe what you're trying to do is``` i -= 1``` instead of a -= 1

Collectives™ on Stack Overflow

Quicksort Partition Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related