Question

Given an list of N integers, Insertion Sort will, for each element in the list starting from the second element: Compare the element with the previous element If the previous element is greater than the element in question (EIQ), push the index of the previous element up 1 Repeat step two with the element before the previous element, and so on. Once an element has been reached that is less than the EIQ, stop pushing and insert the EIQ into the spot ahead of this element (or at the beginning of the list, if it is reached instead).

Answer 1

Answer:

def insSort(arr):

ct=0;

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

key = arr[i]

j = i-1

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

arr[j+1] = arr[j]

j -= 1

ct=ct+1;

arr[j+1] = key

return arr,ct;

print(insSort([2,1]))

Output of the program is also attached.