BlogsDope image BlogsDope

Sorting a list using insertion sort in Python

May 20, 2017 PYTHON ARRAY SORT ALGORITHM LOOP 12523
Download Our App.
BlogsDope App
Get it on Google Play

Insertion sort is similar to arranging the documents of a bunch of students in order of their ascending roll number. Starting from the second element, we compare it with the first element and swap it if it is not in order. Similarly, we take the third element in the next iteration and place it at the right place in the sublist of the first and second elements (as the sublist containing the first and second elements is already sorted). We repeat this step with the fourth element of the list in the next iteration and place it at the right position in the sublist containing the first, second and the third elements. We repeat this process until our list gets sorted. So, the steps to be followed are:

  1. Compare the current element in the iteration (say A) with the previous adjacent element to it. If it is in order then continue the iteration else, go to step 2.
  2. Swap the two elements (the current element in the iteration (A) and the previous adjacent element to it).
  3. Compare A with its new previous adjacent element. If they are not in order then proceed to step 4.
  4. Swap if they are not in order and repeat steps 3 and 4.
  5. Continue the iteration.

The diagram given below will make you understand this better.

Working of insertion sort


Initial list 

16 19 11 15 10

First iteration

16 19 11 15 10

No swapping – 

16 19 11 15 10

Second iteration

16 19 11 15 10

Swap

16 11 19 15 10

Swap

11 16 19 15 10

 Third iteration

11 16 19 15 10

Swap

11 16 15 19 10

Swap

11 15 16 19 10

No swapping –

11 15 16 19 10

Fourth iteration

11 15 16 19 10

Swap

11 15 16 10 19

Swap

11 15 10 16 19

Swap

11 10 15 16 19

Swap

10 11 15 16 19

Python code for insertion sort


a = [16, 19, 11, 15, 10, 12, 14]

#iterating over a
for i in a:
    j = a.index(i)
    #i is not the first element
    while j>0:
        #not in order
        if a[j-1] > a[j]:
            #swap
            a[j-1],a[j] = a[j],a[j-1]
        else:
            #in order
            break
        j = j-1
print (a)

Explanation of the code


for i in a – We are iterating over the list ‘a’

while j>0 – Index of the current element is positive. This means that the element at the index of ‘j’ is not the first element and we need to compare the values.

if a[j-1] > a[j] – These two elements are not in order. We need to swap them. else – The elements are in order, we can break the while loop.

a[j-1],a[j] = a[j],a[j-1] – Swapping.


Liked the post?
Developer and founder of CodesDope.
Editor's Picks
0 COMMENT

Please login to view or add comment(s).