## Quicksort

def swap(array,i,j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

def partition(array, start,end):
    print('->P(',start,end,')')
    x = array[end]
    i = start -1
    for j in range(start, end):

        if (array[j] <= x):
            print('[', array[j], ' <= ', x, '] ?  Y')
            i = i+1
            swap (array,i,j)
        else:
            print('[', array[j], ' <= ', x, '] ?  N')
    swap(array,i+1, end)
    print('insert',end,' at k=',i+1, end='')
    return i+1

def quicksort(array,p,r):
    print('\nQ(', p, r, ')', end='')
    if p<r:
        q = partition(array,p,r)
        quicksort(array,p,q-1)
        quicksort(array,q+1,r)

def main():
    unsortedArray = ['dummy',5,4,3,2,1]
    quicksort(unsortedArray,1,len(unsortedArray)-1)
    print('\n',unsortedArray)

if __name__ == '__main__':
    main()