Insertion Sort in Python

Insertion Sort in Python

Insertion sort is also one of the common sorting technique used. In this technique sorting place after each element encounter. Story of sorting is very simple. Very first node is ignored as it is known as sentinel node. Now from second element will be chosen for sorting. The insertion sort technique checks it position in 0 to n-1 element in the same list where n is the current position and insert the element. This works get repeated till the last element gets sorted. So you will observe that after every elements sorting the list get sorted till the element position. Here is the code and example of Insertion sort.

lst = [15, 6, 13, 22, 3, 52, 2]
print("original list is - ", lst)
for i in range(1, len(lst)):
    key = lst[i]
    j = i - 1
    while j >= 0 and key < lst[j] :
        lst[j + 1] = lst[j]
        j = j - 1        
    else :
        lst[j + 1] = key
    print("List after {0} pass - ".format(i),lst)
print('Now sorted list is - ', lst)

Now we will see the output of the code –

original list is – [15, 6, 13, 22, 3, 52, 2]
List after 1 pass – [6, 15, 13, 22, 3, 52, 2]
List after 2 pass – [6, 13, 15, 22, 3, 52, 2]
List after 3 pass – [6, 13, 15, 22, 3, 52, 2]
List after 4 pass – [3, 6, 13, 15, 22, 52, 2]
List after 5 pass – [3, 6, 13, 15, 22, 52, 2]
List after 6 pass – [2, 3, 6, 13, 15, 22, 52]
Now sorted list is – [2, 3, 6, 13, 15, 22, 52]

Thank you. If you have any query you can ask and post comments to me. I will try to reply.