Insertion Sort | Python

 

Algorithm

An array of size n:
for i=1 to n-1:

    key = arr[i]

    j = i - 1

    while(j >= 0 and key < arr[j]):

        arr[j+1] = arr[j]

        j = j - 1

    arr[j+1] = key

i = i + 1

------------------------------------Code-----------------------------------------

def insertion_sort(alist):

for i in range(1,len(alist)):

key=alist[i]

j=i-1

while(j >= 0 and key < alist[j]):

#moving one element to up

alist[j+1]=alist[j]

j=j-1

alist[j+1]=key

if __name__ == "__main__":

alist=input('Enter the list of numbers: ').split()

#here I use list comprehenssion method to reduce my line of code.

alist=[int(x) for x in alist]

insertion_sort(alist)

print(f'Your sorted list is: {alist}')

----------------------------Complexity-------------------------------

Worst Complexity: n^2

Average Complexity: n^2

Best Complexity: n

Space Complexity: 1