Insertion Sort Algorithm

Write a Python  Program to perform insertion sort. 

Program Algorithm:

1. Create a function named insertionsort

2. Initialise currentvalue=alist[index] and position=index

3. while position>0 and alist[position-1]>currentvalue, perform the following till len(alist)

4. alist[position]=alist[position-1]

5. position = position-1

6. alist[position]=currentvalue

7. Print the sorted list 

Program Code:

def insertionSort(alist):

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

 currentvalue = alist[index]

 position = index

 while position>0 and alist[position-1]>currentvalue:

 alist[position]=alist[position-1]

 position = position-1

 alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]

insertionSort(alist)

print(alist)  

Program Output:

 [17, 20, 26, 31, 44, 54, 55, 77, 93]