Insertion sort in Python
Introduction
Insertion sort is a simple in place (i.e no need for an auxiliary memory) sorting algorithm. It is an efficient algorithm for small data sets, specially for lists that are partially sorted.
- For more information about how sorting works, you may refer to the following article
- For more in depth information about insertion sort you may check the following loop invariant article
Insertion sort explained
Insertion sort is fairly easy to visualize (see the diagram above). Here is a summary of the steps:
- Start with an unsorted list
- The first element from the left is already sorted because it is a single element
- Go to the second element and compare it with the first. If they are out of order then swap them
- Go to the third then go back all the way to the left comparing it with the previous element. Do the swaps as necessary
- Note that at any point in time, the list is split at position (i) into two sublists. The left side of (i) is sorted and the right side (including (i)) is not sorted
- Pick the next element from the unsorted part and put it in the right position in the sorted part
- The position that separates the sublists (i) goes from 1 (second element) to the end of the list
- The element at position (j) that we need to put in the right place goes from wherever (i) is and goes down to the left all the way to its correct position
- We keep shifting that number until it lands in the right position. We do that by swapping
Here is a cool video on youtube demonstrating insertion sort visually in Romanian folk dance
Running time
Insertion sort algorithm has two nested loops. The outer loop index (i) goes from 1 to (n) where (n) is the number of elements in the list. The inner loop index (j) goes from (i) down to wherever the next sorted item needs to be positioned. This is not perfectly (n) times however for large lists and in worst case scenarios it is practically (n) so in big O notation, the running time is O(n^2).
Here is a summary of insertion sort running time:
- The best case scenario for insertion sort happens when the input list is already sorted. In this case the running time is linear O(n) because the inner loop has no effect
- A worst case scenario can happen when the input list is sorted in reverse order. In this case, the running time is O(n^2) because the inner loop will shift the entire sorted sublist before inserting the next element in its correct position
For more information about running time of an algorithm, you may refer to the following article.
Insertion sort in python code
Here is an example insertion sort python algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
# insertion sort python example A = [10, -9, 7, 1, 3] # Print the list before sorting print(A) # (i) is where the list is split into two parts # Elements to the left of (i) are sorted # Elements to the right including (i) are not i = 1 # (i) goes from 1 (second element) to (n) while i < len(A): # (j) goes from (i) down to where the next # element needs to be in the correct position j = i # Keep comparing the element that we need to # sort with elements on the left side of (i) # as long as it is smaller and (j) must be # greater than 0 otherwise we go out of bounds while j > 0 and A[j-1] > A[j]: # Swap the values of A[j] and A[j-1] x = A[j] A[j] = A[j-1] A[j-1] = x # Recall (j) is going down as # we move from right to left j -= 1 # Recall (i) goes from left to right i += 1 # Print the list on every iteration so that # we can see how the sorting is taking place print (A) |
If you run the code snippet above, you should get the following output:
1 2 3 4 5 |
[10, -9, 7, 1, 3] [-9, 10, 7, 1, 3] [-9, 7, 10, 1, 3] [-9, 1, 7, 10, 3] [-9, 1, 3, 7, 10] |
Thanks for reading. For questions or feedback, please use the comment section below.