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:

CodePudding user response：

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