Partition algorithm

""" Below is the partition algorithm commonly used in the QuickSort and QuickSelect algorithms. This function partitions the array in place and returns the index where the pivot element is placed. Elements smaller than or equal to the pivot are placed on the left, and elements greater than the pivot are placed on the right.

the things I would expect people would be most likely to mess up are:
- you're incrementing up to the element *right before* the last one.
- you're checking if the current element is less than *or equal to* the pivot value.
"""

def partition(arr, l=None, r=None):
    if l is None:
        l, r = 0, len(arr)-1
    pivot_starting_index = r
    pivot_value = arr[pivot_starting_index]
    pivot_final_index = l
    for j in range(l, r):
        if arr[j] <= pivot_value:
            arr[pivot_final_index], arr[j] = arr[j], arr[pivot_final_index]
            pivot_final_index += 1
    arr[pivot_final_index], arr[pivot_starting_index] = arr[pivot_starting_index], arr[pivot_final_index]
    return pivot_final_index

arr = [10, 7, 8, 9, 1, 5]
print(partition(arr), arr)