[python-quick-sort] quick sort implmentation #python #algorithm

qsort.py

def qsort(nums):
    qsort_impl(nums, 0, len(nums)-1)
    return nums

def qsort_impl(nums, start, end):
    if start >= end: return
    pivot = partition(nums, start, end)
    qsort_impl(nums, start, pivot-1)
    qsort_impl(nums, pivot+1, end)

def partition(nums, start, end):
    if start >= end: return end

    i_v, v = start, nums[start]
    while start <= end:
        while start <= end and nums[start] <= v: start += 1
        while start <= end and nums[end] > v: end -= 1
        if start > end: break
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1

    nums[end], nums[i_v] = nums[i_v], nums[end]
    return end