python: quicksort debugging

Question

I am trying to implement quicksort, but I am unable to determine why I am seeing this error. I am recursively calling the sort fn which in turn calls partition fn.

ERROR:

[5, 2, 1, 6, 3, 89, 7869, 190, 3, 4, 5, 67]
[5, 2, 1, 6, 3, 5, 4, 3, 67, 7869, 89, 190]
[5, 2, 1, 6, 3, 5, 4, 3, 67, 7869, 89, 190]
[5, 2, 1, 6, 3, 5, 4, 3, 67, 89, 190, 7869]
[5, 2, 1, 6, 3, 5, 4, 3, 67]
Traceback (most recent call last):
  File "ch13.py", line 30, in <module>
    print(sort(A, L, R))
  File "ch13.py", line 22, in sort
    sort(A[:pivot_idx - 1], 0 , pivot_idx - 1)
  File "ch13.py", line 21, in sort
    pivot_idx =  partition(A, L, R)
  File "ch13.py", line 9, in partition
    while A[R] > pivot:
IndexError: list index out of range

IMPLEMENTATION:

def partition(A, L, R):
    # taking pivot as mosr right-element of array
    print(A)
    pivot = A[-1]
    pivot_index = len(A) - 1
    while True:
        while A[L] < pivot:
            L = L + 1
        while A[R] > pivot:
            R = R - 1
        if L >= R:
            break
        A[L], A[R] = A[R], A[L]
        L = L + 1
    A[pivot_index], A[L] = A[L], A[pivot_index]
    print(A)
    return L

def sort(A, L, R):
    if len(A)<=1: return
    pivot_idx =  partition(A, L, R)
    sort(A[:pivot_idx - 1], 0 , pivot_idx - 1)
    sort(A[pivot_idx - 1 :], pivot_idx + 1, R)
    return A

A = [5,2,1,6,3,89,7869,190,3,4,5,67]
L = 0
R = len(A) - 2
partition(A, L, R)
print(sort(A, L, R))

if possible, please explain your fix and point where I was doing wrong.

Answer 1

The code is a variation of Hoare partition scheme, where the pivot and any elements equal to the pivot can end up anywhere after a partition step, so the swap A[pivot_index], A[L] = A[L], A[pivot_index] should not be used. What is being returned is just some "midpoint" index, where elements <= pivot are to the left, and elements >= pivot are to the right, with elements == pivot on either side. It's simpler to implement a post increment | post decrement variation of Hoare by including partition code in the quicksort function and using both indexes:

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + (hi-lo)/2];    // for python use: // 2 for integer divide
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];         // swap a[i], a[j]
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);      // i = (a[i] == p) ? j+2 : j+1
}