quick_sort.py

def partition(arr, low, high):
    pivot = arr[high] # pivot is the last element of the array
    i = (low - 1) # index of the smaller element, it starts with -1
    # j : increments through the array and checks with the pivot if it is greater or smaller
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            # swapping logic
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1] # swaping the pivot value now
    return (i+1)

def quicksort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)
        quicksort(arr, p + 1, high)
        
arr = [9, 3, 1, 0, 3, 10, 0, 22, 16, 15]
quicksort(arr, 0, len(arr)-1)
print('Sorted Array: ', arr)