Python - Insertion Sort Algorithm Implementation

Insertion sort algorithm - In the last couple of articles, we studied Bubble sort and Selection sort algorithms. In this article, we will learn about another sorting algorithm - Insertion sort. Just like Bubble sort and selection sort, time complexity of this algorithm is O(n^2) and space complexity being O(1).

Selection Sort Algorithm

1. First element i.e. element at index 0 is always sorted and is the part of sorted sub-list
2. Select next element
3. Compare it with all elements in sorted sub-list
4. If the value of the element is smaller, swap it with the element(s) in sorted sub-list
5. Continue till we get an element from sorted sub-list which is smaller than the element
6. Insert the element in the sorted sub-list
7. Get the next element
7. Repeat this process for selected element

Example

Consider the following list-

Initially, the first element in the list is already sorted. Hence we add that to sorted sub-list identified with green color.

Iteration 1:
Compare element at index 1 with the elements in sorted sub-list and insert at appropriate location. Here, array > array, so array should appear before array. Hence we swap them to adjust their positions.

Iteration 2:
In this case, array > array, hence nothing needs to be required as it is already at appropriate position.

Iteration 3:
In this case, array < array, so we swap them so that array=7 and array=1. Now, array which is 1 is again less than array, so we swap them again such that array=1 and array=5. Now also, array > array, so we swap these elements such that array=1 and array=3 and we are done.

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

Python Implementation:

def insertion_sort(array):

n = len(array)

for i in range(1, n):
j = i
current = array[j]
while j > 0 and array[j-1] > current:
array[j] = array[j-1]
j -= 1
array[j] = current

my_array = [5, 3, 7, 1,4, 8, 2, 6]
insertion_sort(my_array)
print my_array

Output:

[1, 2, 3, 4, 5, 6, 7, 8]