Implementing The Insertion Sort Algorithm in Python

This tutorial was built using Python 3.6

In this tutorial we are going to be taking a look at the insertion sorting algorithm and how it works as well as how you can implement this algorithm in the Python programming language.

Insertion Sorting

So the insertion sorting algorithm is a well known sorting algorithm that can sort an unsorted array in a worst case time of O(N^2) time. It works by iterating through an array and sorting elements in a linear fashion.

• The algorithm starts at element 0 in an array and considers element sorted.
• It then looks at the first element to the right of our sorted array that just contains our 0 position element
• It then inserts this unsorted element in to it’s correct location.
• Our sorted array now has 2 elements
• The algorithm proceed to insert the next element into the correct position in our sorted array until the entire list has been sorted.

Implementing it in Python

Implementing it in Python can be done like so:

## Insertion Sort In Python
#
## Performance Complexity = O(n^2)
## Space Complexity = O(n)

def insertionSort(my_list):
    ## for every element in our array
    for index in range(1, len(my_list)):
        current = my_list[index]
        position = index

        while position > 0 and my_list[position-1] > current:
            print("Swapped {} for {}".format(my_list[position], my_list[position-1]))
            my_list[position] = my_list[position-1]
            print(my_list)
            position -= 1

        my_list[position] = current

    return my_list

my_list = [8,2,1,3,5,4]

print(insertionSort(my_list))

When executed this should give you the following output:

 $ python3.6 insertionSort.py
Swapped 2 for 8
[8, 8, 1, 3, 5, 4]
Swapped 1 for 8
[2, 8, 8, 3, 5, 4]
Swapped 8 for 2
[2, 2, 8, 3, 5, 4]
Swapped 3 for 8
[1, 2, 8, 8, 5, 4]
Swapped 5 for 8
[1, 2, 3, 8, 8, 4]
Swapped 4 for 8
[1, 2, 3, 5, 8, 8]
Swapped 8 for 5
[1, 2, 3, 5, 5, 8]
[1, 2, 3, 4, 5, 8]