What's wrong with this implementation of quicksort?

Question

I'm trying to implement the quicksort algorithm choosing the pivot as the rightmost element as described in Cormey et al., Introduction to Algorithms:

Here is my Python implementation:

def partition(A, p, r):
    pivot = A[r]
    i = p - 1
    for j in range(p, r-1):
        if A[j] < pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

However, if I try to test it like so:

A = [2, 8, 7, 1, 3, 5, 6, 4]
quicksort(A, 0, len(A)-1)
print(A)

I get an array which is not sorted but just partitioned once:

[2, 3, 1, 4, 5, 7, 8, 6]

(That is, all the elements left (right) of the 4 are smaller (greater) than it). It seems that the recursive calls to quicksort are not operating in place on the input array A like the call to partition. How can I fix this?

Ferriferous

Answer 1

The mistake is in partition, exactly in for j in range(p, r-1): : It must be, for j in range(p, r):.

This happens because in Python, the stop index is not included in the range, but the algorithm meant to include r-1, therefore one must stop at r in order to include r-1.

Matchmark