Quick Sort Implementation in Python [particular input crashes]

Question

I'm writing a quick_sort algorithm code. This is the code that should work in my knowledge and which works for most arrays but it doesn't work on [5, 3, 9, 8, 6] and spits out IndexError: list index out of range

def quick_sort_array(A):
    return quick_sort(A, 0, len(A)-1)

def quick_sort(A, l, r):
    if l < r:
        pivot = A[l]
        left = l + 1
        right = r
        while left <= right:
            while A[left] <= pivot:
                left += 1
            while A[right] >= pivot and left <= right:
                right -= 1
            if left <= right:
                tmp = A[left]
                A[left] = A[right]
                A[right] = tmp
        A[l] = A[right]
        A[right] = pivot

        quick_sort(A, l, right-1)
        quick_sort(A, right+1, r)

Can you please help me in understanding this? Thanks

Error Message:

In the call that fails, what are the values of the parameters? That should allow you to quickly find the error. Also, try to find a video tutorial showing you how to step through code with a debugger. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Mar 20, 2022 at 22:06

Blckknght · Accepted Answer · 2022-03-20 21:48:16Z

1

Your implementation of the partition step of Quicksort fails when the pivot is the largest element between the start of part of the list you're partitioning and the end of the list. The while loop that increases left can keep going until it runs off the end of the list.

To fix the issue, you need to stop the first inner loop from running past right, just like you already prevent right from running too far past left. I've not verified exactly what boundary condition you want, but just copying the one from the second inner loop will probably work:

        while A[left] <= pivot and left <= right:
            left += 1
        while A[right] >= pivot and left <= right:
            right -= 1

answered Mar 20, 2022 at 21:48

Blckknght

106k11 gold badges135 silver badges188 bronze badges

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

Collectives™ on Stack Overflow

Quick Sort Implementation in Python [particular input crashes]

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related