Python program to implement Insertion Sort

# Insertion 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="")
    print()

 
def insertion_sort(): # Insertion Sort Block
    global c
    for i in range(1,n):
        key=a[i]
        j=0
        for j in range (i-1,0,-1):
            if a[j]>key:
                c=c+1
                a[j+1]=a[j]
        a[j+1]=key
  

# __________________________ Main Block Starts __________________________  
print("\t\t\t____Insertion 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_sorted()
    print("\nBefore sorting: ")
    showdata()
    insertion_sort()
    print("\nAfter sorting: ")
    showdata()
    print("Theoretical Complexity: ", n)

elif ch == 2: # Average Case
    getdata_random()
    print("\nBefore sorting: ")
    showdata()
    insertion_sort()
    print("\nAfter sorting: ")
    showdata()
    print("Theoretical complexity: ",(n*n))

elif ch == 3: # Worst Case
    getdata_reverse()
    print("\nBefore sorting: ")
    showdata()
    insertion_sort()
    print("\nAfter sorting: ")
    showdata()
    print("Theoretical complexity: ", (n*n))
 
else:
    print("\nInvalid Choice!")
 
print("Runtime Complexity: ", c)

Output