Write Python program to sort n names using Quick sort algorithm. Discuss the complexity of algorithm used.

Code:

 

def quicksort(mylist):

    Quicksort(mylist,0,len(mylist)-1)

 

def Quicksort(mylist,i,j):

    if i<j:

        q=partition(mylist,i,j)

        Quicksort(mylist,i,q-1)

        Quicksort(mylist,q+1,j)

 

def partition(mylist,i,j):

    pivotelement =mylist[i]

    leftval=i+1

    rightval=j

    done=False

    

    while not done :

        while leftval<=rightval and mylist[leftval]<=pivotelement:

            leftval=leftval+1

            

        while mylist [rightval]>=pivotelement and rightval>= leftval:

            rightval =rightval -1

        if rightval<leftval:

            done=True

        else:

            temp=mylist[leftval]

            mylist[leftval]=mylist[rightval]

            mylist[rightval]=temp

 

    temp=mylist[i]

    mylist[i]=mylist[rightval]

    mylist[rightval]=temp

    return rightval

mylist=['ram', 'shyam', 'donald', 'harry', 'henry','john']

print("before applying quicksort technique:",mylist)

quicksort(mylist)

print("after applying quicksort technique",mylist)           

 

O/P:

Fundamental of algorithm