import random

def quicksort(arr: list, low: int, high: int):
    if (low < high):
        pivot = partition(arr, low, high)

        quicksort(arr, low, pivot - 1)
        quicksort(arr, pivot + 1, high)

    pass

def partition(arr: list, low: int, high: int):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

if __name__ == '__main__':
    randomList = [random.randint(1, 100) for x in range(100)]
    print(randomList)

    quicksort(randomList, 0, len(randomList) - 1)

    print(randomList)