quick_sort.py

def quick_sort(array, start, end): # Call by value
    if(start < end):
        pivot_idx = partition(array, start, end)
        quick_sort(array, start, pivot_idx-1)
        quick_sort(array, pivot_idx+1, end)

def partition(array, start, end):
    pivot = array[start]
    l_idx = start
    r_idx = end
    while(l_idx < r_idx):
        while(l_idx < r_idx and pivot <= array[r_idx]):
            r_idx-=1
        if(l_idx < r_idx):
            array[l_idx] = array[r_idx] 
            l_idx+=1
            
        while(l_idx < r_idx and array[l_idx] <= pivot):
            l_idx+=1
        if(l_idx < r_idx):
            array[r_idx] = array[l_idx] 
            r_idx-=1
    array[l_idx] = pivot
    return l_idx

def check(array):
    for i in range(0, len(array)-1):
        if i+1 < len(array):
            assert array[i] <= array[i+1], "[%d]:%d > [%d]:%d" % (i, array[i], i+1, array[i+1])

if __name__ == '__main__':
#    array = [49,38,65,97,76,13,27,49]
    array = [4, 1, 2, 3, 9, 8]
    
    print array
    quick_sort(array, 0, len(array)-1)
    print array
    check(array)