Write a function insertionSort that implements the insertion

Write a function (insertionSort) that implements the insertion sort algorithm, This function will take exactly one argument, and returns a list. The argument is a list of integers to be sorted. You will return a new list which has been sorted in ascending order. Write some code to test your insertion sort with multiple lists. Try to find various cases that would be relevant for a sorting function, so that you test using inputs that are most likely to find errors in your program. Sample output: >>> insertionSort ([4, 3, 7, 1, 8, 2]) [1, 2, 3, 4, 7, 8] modify your code to count the number of a basic operation. For example, a good basic operation to count would be comparisons (=, or ==). Run your program multiple times using various list sizes (keep it under 50 elements), and draw a table comparing input size (N) to the number of operations (P). Make sure your table has at least 8 different values for N, ideally inserted in numerical order into the table. Draw a line chart (e.g. in a spreadsheet program) showing your results.

Solution

# python code

import sys
import re
def insertionSort(inputList):
   totalComparisons = 0
   # one comparsion per for loop to check if i has reached limit
   for i in range(1,len(inputList)):
       totalComparisons = totalComparisons + 1
       currValue = inputList[i]
       currPosition = i
       # two comparisons in envery iteration
       while currPosition>0 and inputList[currPosition-1]>currValue:
           totalComparisons = totalComparisons + 2
           inputList[currPosition]=inputList[currPosition-1]
           currPosition = currPosition-1
       inputList[currPosition]=currValue
   return totalComparisons,inputList

inputList = [4,3,7,1,8,2]
print \"Input list: \",inputList
comparisons,sortedList = insertionSort(inputList)
print \"Sorted List: \", sortedList
print \"Total comparisons: \",comparisons

\'\'\'
output:

Input list: [4, 3, 7, 1, 8, 2]
Sorted List: [1, 2, 3, 4, 7, 8]
Total comparisons: 21

\'\'\'