Insertion sort is a very simple sorting algorithm that is based on the swapping of the elements of the list/array. In the swapping process, it checks if the current element is less than the previous elements. If the current element is less than the previous elements, it exchanges the position, i.e., the current element becomes the previous element, and the previous element becomes the current element. The swapping of the elements is repeated for all elements in the list.
Suppose the 5th element in the list is 8 and the 4th element is 9, then the position of these two elements will be swapped and 9 will become 5th element and 8 will become the 4th element. Now, 4th element is compared with the 3rd element. This process is repeated until the first element of the list is reached. The below Python code performs insertion sort. I have put the output of each step to make the process obvious.
def swap (a1,a2):
x = a1
a1 = a2
a2 = x
return (a1,a2)
def insertion_sort(a):
n = len(a)
for i in xrange(1,n):
j = i
while (j > 0 and a[j-1] > a [j]):
(a[j-1],a[j]) = swap (a[j-1], a[j])
j = j-1
print a
return a
l = [25,24,21,21,20,1,1,9,10,8,3,4,5,1,3,1]
s= insertion_sort(l)
#print s
The output of the above code looks like this…
[24, 25, 21, 21, 20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1]
[21, 24, 25, 21, 20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1]
[21, 21, 24, 25, 20, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1]
[20, 21, 21, 24, 25, 1, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1]
[1, 20, 21, 21, 24, 25, 1, 9, 10, 8, 3, 4, 5, 1, 3, 1]
[1, 1, 20, 21, 21, 24, 25, 9, 10, 8, 3, 4, 5, 1, 3, 1]
[1, 1, 9, 20, 21, 21, 24, 25, 10, 8, 3, 4, 5, 1, 3, 1]
[1, 1, 9, 10, 20, 21, 21, 24, 25, 8, 3, 4, 5, 1, 3, 1]
[1, 1, 8, 9, 10, 20, 21, 21, 24, 25, 3, 4, 5, 1, 3, 1]
[1, 1, 3, 8, 9, 10, 20, 21, 21, 24, 25, 4, 5, 1, 3, 1]
[1, 1, 3, 4, 8, 9, 10, 20, 21, 21, 24, 25, 5, 1, 3, 1]
[1, 1, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25, 1, 3, 1]
[1, 1, 1, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25, 3, 1]
[1, 1, 1, 3, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25, 1]
[1, 1, 1, 1, 3, 3, 4, 5, 8, 9, 10, 20, 21, 21, 24, 25]