Quick Sort

QuickSort.py

def partition(arr, low, high):
    # choose pivot as 
    pivot = arr[high]
    i = -1
    j = 0
    # move all elements that are <= pivot to the left of it 
    # and bigger elements to the right
    while j < high:
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
        j += 1
    i += 1
    arr[i], arr[high] = arr[high], arr[i]
    # return index of pivot
    return i 

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