Python program to implement Quick Sort

# Quick Sort

import random
import math

c = 0 # Counter for Runtime Complexity
A = [] # List of elements
n = 0 # No. of elements

def getdata_random(): # Random Input
    for i in range(n):
        A.append(random.randint(1,n))

def getdata_sorted(): # Sorted Input
    for i in range(n):
        A.append(i+1)
  
def getdata_reverse(): # Reverse Sorted Input
    for i in range(n):
        A.append(n-i)

def showdata(): # Display all elements
    for i in range(n):
        print(A[i],"\t",end="")


def quick_sort(first,last): # Quick Sort block
    global c
    if first < last:
        pivot = first
        i = first
        j = last
        while i<j:
            while A[i]<=A[pivot] and i<last:
                i=i+1
                c=c+1

            while A[j]>A[pivot]:
                j=j-1
                c=c+1
            
            if i<j:
                temp = A[i]
                A[i] = A[j]
                A[j] = temp

        temp = A[pivot]
        A[pivot] = A[j]
        A[j] = temp
        quick_sort(first,j-1)
        quick_sort(j+1, last)


# __________________________ Main Block Starts __________________________
print("\t\t\t____Quick Sort____")  
n=int(input("\nEnter number of elements: "))
print("\n1. Best Case\t2. Average Case\t3. Worst Case")
ch = int(input("\tEnter your choice: "))

if ch == 1: # Best Case
    getdata_random()
    print("\nBefore sorting: ")
    showdata()
    quick_sort(0,n-1)
    print("\nAfter sorting: ")
    showdata()
    print("\nTheoretical Complexity: ",n*math.log(n))             

elif ch==2: # Average Case
    getdata_random()
    print("\nBefore sorting: ")
    showdata()
    quick_sort(0,n-1)
    print("\nAfter sorting: ")
    showdata()
    print("\nTheoretical Complexity: ",n*math.log(n))              

elif ch==3: # Worst Case
    getdata_sorted()
    print("\nBefore sorting: ")
    showdata()
    quick_sort(0,n-1)
    print("\nAfter sorting: ")
    showdata()
    print("\nTheoretical Complexity: ",(n*n)) 
 
else:
    print("Invalid choice!")

print("Runtime Complexity: ",c)
    

Output