Python Insertion Sort Algorithm: Explained with Examples, Code and Video
The insertion sort algorithm is the next simple sorting algorithm in our series.
Insertion Sort Algorithm in Python
The insertion sort algorithm is a simple sorting algorithm that works by repeatedly swapping each element into the correct location in the list.
Starting from the list beginning at index 1, it compares the first two elements and swaps them into order if necessary.
It then repeats this process with the next element to make three ordered elements, then for, and so on. On each pass then new element is ‘inserted’ into the correct position.
Perhaps the best way to understand the insertion sort is to see an example.
for i in range (1, len(nums)):
j = i - 1
while j >= 0:
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
j = j -1
Insertion Sort in Python Example
The insertion sort also uses the process of swapping elements if they are not in order, as we have seen with the bubble and selection sorts. In this example we use the varaible j and j+1.
#swap numbers
nums[j],nums[j+1] = numsj[+1],nums[j]The example starts with the same example seen in the previous two sorting algorithms.
The first pass compares the first two elements, and in this example, the second element, 1, is lower then the first, 7, therefore they are swapped.
The second pass does not alter the list as 1,7 and 8 are in order. But the third pass moves the four down to the correct place in the list.
The next pass takes the element with the number 3 and moves it down the list t its correct position.
The final pass in our example moves the final element, 2, down the list, swapping with the previous element.
Once the final pass has correctly inserted the final element into its correct position, the list is in order.
Video Tutorial
Insertion Sort in Python Explained
We use the variable i, starting at index 1, to iterate through the list ordering the first two elements, the first three elements, and so on.
We compare the new element with the numbers before it to move it into the correct position in the list.
In the example, we moved the 1, no change on pass 2, then the 4 into position, then the 3, then finally the 2.
nums = [7,1,8,4,3,2]
for i in range(1,len(nums)):
key = nums[i]
j = i-1
print(key,nums)
while j >= 0 and key < nums[j]:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
print(nums)In the python code, this number that we move is the key, and we loop using the variable j back to the beginning of the list, comparing the elements at j and j+1.
If our key is not lower than the element before it, we can stop that pass.
In the final example of the insertion sort algorithm in python, there are print statements added to see the list at each iteration before any items are swapped.
output
[7, 1, 8, 4, 3, 2]
[1, 7, 8, 4, 3, 2]
[1, 7, 8, 4, 3, 2]
[1, 4, 7, 8, 3, 2]
[1, 3, 4, 7, 8, 2]
[1, 2, 3, 4, 7, 8]
The code can be downloaded and copied from this text file – insertion_sort.txt
Compare Insertion, Selection, and Bubble Sort Algorithms in Python
Although it is common to use order of magnitude to compare algorithms, to show the three algorithms in python we compare the runtime.
A collection of 1000 unordered list of six numbers, ranging from 1 to 100 were randomly created. The three algorithms seen above were then placed in functions and applied on the lists.
We use a start and stop timer to measure the length in time that each sorting algorithm takes on the 1000 list of random lists, to order, or sort the numbers into order.
The results differ but we can generalize to give an overview.
The fastest algorithm of the three sorting algorithms was consistently the insertion sort. This completed the task in about 2 milliseconds.
The performance of the selection sort came second, taking about 3.2 to 3.5 milliseconds, sometimes a little less.
The bubble sort was consistently the slowest of the three algorithms on nearly every occasion, although there were the odd occasion when the selection sort was slower.
The bubble sort was about 0.3 to 0.4 milliseconds slower than the selection sort, at about 3.5-3.8 milliseconds.
The python code is available in the following document, you are welcome to copy the code into a python file – compare sorting algorithms in python code.
