Python Insertion Sort

Let’s study the Python Insertion Sort algorithm, a very simple sorting algorithm to implement.

The algorithm works in a very similar way to the way we arrange playing cards in our hand.

In fact, it is assumed that the first card is ordered, then an unsorted card is taken and placed on its left if it is smaller, on its right if it is greater. This way the unsorted cards will be put in their place.

The Insertion Sort sorting algorithm works in a very similar way.

Suppose the starting list is this:

numbers = [3,6,1,9,2]

The list is scrolled from position i which goes from 1 to n, then from number 6 to number 2.

So if the element of the list in position i is greater than its predecessor it does not move, if instead it is smaller it moves to the left until a smaller predecessor is found or the leftmost position of the array is reached.

Python Insertion Sort – code

We define an insertion_sort function that takes the list as a parameter.

We create a for loop that scrolls the elements of the list from a to 1 up to its length, we store the element to be compared in a temp variable and assign the previous element of index i to j.

Then with a while loop we continue until the element to be compared is smaller than its predecessors or reaches the leftmost position (ie the one with index 0). From time to time we exchange the element and decrease the variable j.

After the while loop, in any case, we assign the value of temp to a [j + 1], even if there have been no exchanges.

So here is our Python Insertion Sort code:

def insertion_sort(a):
    for i in range(1, len(a)):  
        temp = a[i] #first item to compare
 
        j = i-1 #the first time is the first element
        while j >= 0 and temp < a[j]:
                a[j+1] = a[j]
                j -= 1
        a[j+1] = temp
       
a = [3,6,1,9,2]
insertion_sort(a)
print(a)

We could also avoid using the temporary variable by assigning the variable i to j. Here is a possible implementation:

def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j - 1] > a[j]:
            a[j], a[j - 1] = a[j - 1], a[j]
            j -= 1
       
a = [3,6,1,9,2]
insertion_sort(a)
print(a)

We can try our code in the editor below:

In this lesson we have developed the Python Insertion Sort algorithm, in the next we will study other sorting arlgorithms.

Useful links

Python Tutorial

1. Introduction to dictionaries in Python
2. Use Python dictionaries
3. Create dictionaries in Python
4. Python get() method
5. keys() method
6. items() method
7. pop() method
8. popitem() method
9. Sort dictionary in Python