Quick Sort Python Program

Question

I'm trying to figure out why my program isn't fully sorting the arr, here's the code below, output: [7, 9, 6, 1, 5, 10, 15, 7, 2]. Maybe my partition function is wrong.

def quickSort(arr, lower_bound, upper_bound):

    if lower_bound >= upper_bound:
        return

    if lower_bound < upper_bound:
        loc = partition(arr, lower_bound, upper_bound)
        quickSort(arr, lower_bound, loc-1)
        quickSort(arr, loc+1, upper_bound)

def partition(arr, lower_bound, upper_bound):
    pivot = arr[lower_bound]
    start = lower_bound
    end = upper_bound

    while start < end:
        while start <= end and arr[start] <= pivot:
            start += 1
        while start <= end and arr[end] >= pivot:
            end -= 1

        if start < end:
            arr[start], arr[end] = arr[end], arr[start]
        else:
            break

    arr[start], arr[end] = arr[end], arr[start]

    return end

arr = [7, 6, 10, 5, 9, 2, 1, 15, 7]
quickSort(arr, 0, len(arr)-1)

print(arr)

Answer 1

The error is in the line after the while loop:

arr[start], arr[end] = arr[end], arr[start]

When execution arrives at this statement, start and end are equal, so this accomplishes nothing. After the while loop ends, the pivot value -- which is still sitting at lower_bound -- should be moved to where start and end have met. So correct to:

arr[lower_bound], arr[end] = arr[end], pivot

And now return end is doing what it should do: return the index where the pivot element is sitting, separating the not-greater values (left) from the not-smaller values (right).