quick_sort.py

from random import randint

def quick_sort(arr, start, end):
    if start >= end:
        return arr
    
    pivot_idx = partition(arr, start, end) 
    quick_sort(arr, start, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, end)

    return arr

def partition(arr, start, end):
    partition_idx = randint(start, end)
    arr[partition_idx], arr[end] = arr[end], arr[partition_idx]
    i = start
    for j in range(start, end):
        if arr[j] <= arr[end]:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[end] = arr[end], arr[i]
    
    return i