To write a Python Program to perform insertion sort.

 Aim:

To write a Python Program to perform insertion sort.

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:

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)

Sample Output:

$python main.py [20, 54, 54, 54, 54, 54, 93, 93, 93]