CODEWITHSUNDEEP
arrayspython-3.xalgorithmrecursionquicksort
Noah Hoefle
Noah Hoefle

Reputation: 11

Quicksort Partition Python

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.

Upvotes: 1

Views: 1188

Answers (1)

M Oehm
M Oehm

Reputation: 29126

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()

Upvotes: 1

Related Questions