Quicksort Python Program

Quicksort is a sorting technique with algorithmic complexity of O(nlogn). This sorting technique too falls under divide and conquer technique like Merge Sort.  In this post we will discuss the concept and working of this extremely popular sorting mechanism. We will write and explain the Quicksort Python Program using stacks to store sub-lists that are created while dividing.

Quicksort-Working

The basic logic of Quicksort is that after each cycle one element called the pivot element reaches it correct position. It means all elements smaller than the pivot element, are on its left and all elements larger than the pivot element are on its right. This pivot element can be the first, the last or the middle element.  Here we will consider the first element of the unsorted list as the pivot element.

Locate Smaller Elements from Right to Left

The list is scanned from right to left looking for an element smaller than the pivot element. When such element is located, interchange between smaller element and pivot element is done. The index of the pivot element is also updated with the index where interchange is done.

Locate Bigger Elements from Left to Right

Next the unsorted list is scanned from left to right looking for an element bigger than the pivot element. When such an element is located, it is interchanged with the pivot element. The index of pivot element is also updated with the index of the bigger element with which interchange is done.

This scanning from right to left and left to right while interchanging the elements is repeated unless the pivot element’s index and current element’s index are equal. This is the situation when pivot element has taken its correct position in such a way that all the elements to its left are smaller and all the elements on its right are bigger than the pivot element.

Create Sub-lists Excluding Pivot Element

The index of the pivot element is then used to divide the list into two sub lists. Left sub list has elements with index of first element of sub list to 1 less than the index of the pivot element. Right sub list is from index value the index of pivot element+1 to the index of the last element of the sub list. Every newly created sub list’s boundaries are maintained by pushing into the stacks called lower and upper. The sorting process ends when these stacks become empty.

Quicksort Python Program

In this code the lists lower and upper are used as stacks to maintain the boundaries of sub lists created by division after a pivot element takes it correct position. append() function of Python list is used to push and pop() function is used to pop stack elements.

def quick(arr,first,last,dr):
    i=first
    j=last
    pivot=first
    while(1):
        if dr=='rl': #scan from right to left to find an element smaller than pivot
            while arr[pivot]<=arr[j] and pivot!=j:
                j=j-1
            if pivot==j:#stop if scanning crosses pivot index
                dr='nn'
            if arr[pivot]>arr[j]:#Interchange pivot element and smaller element on right
                temp=arr[j]
                arr[j]=arr[pivot]
                arr[pivot]=temp
                pivot=j
                dr='lr'#change direction of scanning
            continue        
        if dr=='lr':#scan from left to right to find an element bigger than pivot
            while arr[pivot]>=arr[i] and pivot!=i:
                i=i+1
            if pivot==i:#stop if scanning crosses pivot index
                dr='nn'
            if arr[pivot]<arr[i]:#Interchange pivot element and bigger element on left
                temp=arr[i]
                arr[i]=arr[pivot]
                arr[pivot]=temp
                pivot=i
                dr='rl' #change direction of scanning
            continue 
        if dr== 'nn':
            break
    return pivot     #return correct position of pivot element
         
def quicksort(arr,num):
    beg=0
    end=0
    mid=0
    top=0
    #initialise stacks to store sublist stast and end indices
    lower=[]
    upper=[]
    #push array boundaries
    lower.append(0)
    upper.append(num-1)
    while (top!=-1):
        #pop boudaries of a sublist
        beg=lower.pop()
        end=upper.pop()
        top=top-1
        #call quick to place first element at correct position and get it indes
        mid=quick(arr,beg,end,'rl')
        #create sublists by excluded correctly placed pivot element
        if (beg<mid-1):
            #push left sublist boundaries
            lower.append(beg)
            upper.append(mid-1)
            top=top+1
        if (mid+1<end):
            #push right sublist boundaries
            lower.append(mid+1)
            upper.append(end)
            top=top+1
        
#display data of the array        
def disparr(arr,n ):
    i=0
    print("Array elements are--->")
    while (i<n):
        print(arr[i])
        i=i+1
      
arrlist=[]
n=0
t=0
n=int(input("Number of elements you want to add--->"))
while (t<n):
    arrlist.append(int(input("input value--->")))
    t=t+1
print("Before Sorting:")
disparr(arrlist,n)
quicksort(arrlist,n)
print("After Sorting:")
disparr(arrlist,n)

Output Quicksort Python Code

admin