

def partition(arr: list[int], low: int, high: int):

    # choose the last element as pivot
    pivot = arr[high]
    # Pointer for greater element
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            # If element smaller than pivot is found
            # swap it with the greater element pointed by i
            i += 1

            # Swapping element at i with element at j
            arr[i], arr[j] = arr[j], arr[i]
    
    # Swap the pivot element with 
    # e greater element specified by i
    arr[i+1], arr[high] = arr[high], arr[i+1]

    # Return the position from where partition is done
    return i+1

def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        # Sort left
        quick_sort(arr, low, pivot-1)
        # Sort right
        quick_sort(arr, pivot+1, high)

test_quick_sort = [5, 3, 2, 10, 7, 1, 4, 8]
print(f"Array {test_quick_sort} before quick sort")
quick_sort(test_quick_sort, low=0, high=len(test_quick_sort)-1)
print(f"Array {test_quick_sort} after quick sort")

3604c4392f25f076aaadcc3d471e53c1827bf1cc
def partition(arr: list[int], 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


<mask token>

def partition(arr: list[int], 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


def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort(arr, low, pivot - 1)
        quick_sort(arr, pivot + 1, high)


<mask token>

def partition(arr: list[int], 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


def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort(arr, low, pivot - 1)
        quick_sort(arr, pivot + 1, high)


<mask token>
print(f'Array {test_quick_sort} before quick sort')
quick_sort(test_quick_sort, low=0, high=len(test_quick_sort) - 1)
print(f'Array {test_quick_sort} after quick sort')

def partition(arr: list[int], 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


def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort(arr, low, pivot - 1)
        quick_sort(arr, pivot + 1, high)


test_quick_sort = [5, 3, 2, 10, 7, 1, 4, 8]
print(f'Array {test_quick_sort} before quick sort')
quick_sort(test_quick_sort, low=0, high=len(test_quick_sort) - 1)
print(f'Array {test_quick_sort} after quick sort')



def partition(arr: list[int], low: int, high: int):

    # choose the last element as pivot
    pivot = arr[high]
    # Pointer for greater element
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            # If element smaller than pivot is found
            # swap it with the greater element pointed by i
            i += 1

            # Swapping element at i with element at j
            arr[i], arr[j] = arr[j], arr[i]
    
    # Swap the pivot element with 
    # e greater element specified by i
    arr[i+1], arr[high] = arr[high], arr[i+1]

    # Return the position from where partition is done
    return i+1

def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        # Sort left
        quick_sort(arr, low, pivot-1)
        # Sort right
        quick_sort(arr, pivot+1, high)

test_quick_sort = [5, 3, 2, 10, 7, 1, 4, 8]
print(f"Array {test_quick_sort} before quick sort")
quick_sort(test_quick_sort, low=0, high=len(test_quick_sort)-1)
print(f"Array {test_quick_sort} after quick sort")
