Python program to implement Standard Sorting Algorithms

# Standard Sorting Algorithms

import random
import math

c=0 # c is a counter to compute Runtime Complexity
A=[]
n=0

def getData():
    for i in range(n):
        A.append(random.randint(0,n)) # Arbitrary Inputs

def sgetData():
    for i in range(n):
        A.append(i+1) # Sorted Inputs

def rgetData():
    for i in range(n):
        A.append(n-i) # Reverse Sorted Inputs

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


# __________________________ Bubble Sort __________________________
def BubbleSort():
    global c
    for i in range(n):
        flag=0
        for j in range(n-i-1):
            c=c+1
            if A[j] > A[j+1]:
                temp=A[j]
                A[j]=A[j+1]
                A[j+1]=temp
                flag=1
            
        if flag==0:
            break


# __________________________ Selection Sort __________________________
def find_max_pos(last): # Returns position of the max element
    global c
    max_val=A[0]
    max_pos=0
    for i in range(1, last+1):
        c=c+1
        if A[i]>max_val:
            max_val=A[i]
            max_pos=i
        
    return(max_pos)

def SelectionSort():
    global c
    for i in range(n-1, 0, -1): # Reverse loop from n-1 to 0
        c=c+1
        max_pos=find_max_pos(i)
        temp=A[i]
        A[i]=A[max_pos]
        A[max_pos]=temp


# __________________________ Insertion Sort __________________________
def InsertionSort():
    global c
    for i in range(1, n):
        key=A[i]
        j=0
        for j in range(i-1, 0, -1): # Reverse loop from i-1 to 0
            if A[j]>key:
                c=c+1
                A[j+1]=A[j]
        A[j+1]=key


# __________________________ Quick Sort __________________________
def QuickSort(first, last):
    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

        QuickSort(first,j-1)
        QuickSort(j+1,last)
    

# __________________________ Merge Sort __________________________
def Merging(x, p, y): # Merges two sorted array
    global c
    i=x;
    j=p+1;
    k=x;
    B=[0] * (x+y+1)
    while i<=p and j<=y:
        c=c+1
        if A[i] < A[j]:
            B[k]=A[i]
            i=i+1
        else:
            B[k]=A[j]
            j=j+1
        k=k+1
    
    while i<=p:
        c=c+1
        B[k]=A[i]
        k=k+1
        i=i+1

    while j<=y:
        c=c+1
        B[k]=A[j]
        k=k+1
        j=j+1   

    for l in range(x, y+1):
        A[l]=B[l];

def MergeSort(x, y):
    global c
    if x<y:
        p=(x+y) // 2
        MergeSort(x,p)
        MergeSort(p+1,y)
        Merging(x,p,y)  


# __________________________ Main Block Starts __________________________
print("\t\t\t____Standard Sorting Algorithms____")
n=int(input("Enter number of elements: "))

print("\n\t1. BubbleSort\t2. SelectionSort\t3. InsertionSort\t4. QuickSort\t5. Merge")
ch=int(input("\tEnter your choice: "))

if ch==1:
    print("\n\t1. Best Case\t2. Average Case\t3. Worst Case")
    ch2=int(input("\t\tEnter your choice: "))
    
    if ch2==1:
        sgetData()
        print("\nBefore sorting: ")
        showdata()
        BubbleSort()
        print("Theoretical Complexity: ",n)     

    elif ch2==2:
        getData()
        print("\nBefore sorting: ")
        showdata()
        BubbleSort()
        print("Theoretical Complexity: ",(n*n))     

    elif ch2==3:
        rgetData()
        print("\nBefore sorting: ")
        showdata()
        BubbleSort()
        print("Theoretical Complexity: ",(n*n))     

    else:
        print("Invalid choice!")
    
    print("Runtime Complexity: ",c)

elif ch==2:
    getData()
    print("\nBefore sorting: ")
    showdata()
    SelectionSort()
    print("Runtime Complexity: ",c)
    print("Theoretical Complexity: ",(n*n))
    
elif ch==3:
    print("\n\t\t1. Best Case\t2. Average Case\t3. Worst Case")
    ch2=int(input("\t\tEnter your choice: "))
    
    if ch2==1:
        sgetData()
        print("\nBefore sorting: ")
        showdata()
        InsertionSort()
        print("Theoretical Complexity: ",n)
                
    elif ch2==2:
        getData()
        print("\nBefore sorting: ")
        showdata()
        InsertionSort()
        print("Theoretical Complexity: ",(n*n))                     

    elif ch2==3:
        rgetData()
        print("\nBefore sorting: ")
        showdata()
        InsertionSort()
        print("Theoretical Complexity: ",(n*n))                     

    else:
        print("Invalid choice!")
    
    print("Runtime Complexity: ",c)
            
elif ch==4:
    print("\n\t\t1. Best Case\t2. Average Case\t3. Worst Case")
    ch2=int(input("\t\tEnter your choice: "))
    if ch2==1:
        getData()
        print("\nBefore sorting: ")
        showdata()
        QuickSort(0,n-1)
        print("Theoretical Complexity: ",n*math.log(n))             

    elif ch2==2:
        getData()
        print("\nBefore sorting: ")
        showdata()
        QuickSort(0,n-1)
        print("Theoretical Complexity: ",n*math.log(n))             

    elif ch2==3:
        sgetData()
        print("\nBefore sorting: ")
        showdata()
        QuickSort(0,n-1)
        print("Theoretical Complexity: ",(n*n))
                
    else:
        print("Invalid choice!")
    
    print("Runtime Complexity: ",c)
    
elif ch==5:
    getData()
    print("\nBefore sorting: ")
    showdata()
    MergeSort(0, n-1)
    print("Runtime Complexity: ",c)
    print("Theoretical Complexity: ",(n*math.log(n)))           

else:
    print("Invalid choice!")

print("\nAfter sorting: ")
showdata()

Output