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.
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