Have you ever sorted playing cards in your hand? That’s one way to think about the concept of Python insertion sort. When you need to sort a list with only a few elements, the insertion sort has your back.
Insertion sorts place an unsorted element in its correct place after each iteration in an array.
In this guide, we’re going to talk about what insertion sorts are and how they work. We’ll discuss how to implement an insertion sort in Python, with reference to an example, so you can get started with this sorting algorithm.
What is a Python Insertion Sort?
An insertion sort divides a list into two sublists: sorted and unsorted. It then compares each element in the unsorted list and continues to do so until each element is sorted.
Each time a comparison is performed, the sorted item is moved into the sorted sublist. Both sublists are part of the same array.
One way to think about insertion sorts is like how you would sort a set of cards in your hand if you were playing a card game. You’d move one-by-one through the list of cards and compare them with each other. The sorted cards would appear in the left of your hand. The unsorted cards would appear on the right until you sort them all.
When Should You Use an Insertion Sort?
Insertion sorts are best used when the data in a list is either nearly sorted, or when you are sorting a small list. There are more efficient algorithms that you can use to sort large lists. For instance, a merge sort or a quick sort is faster.
Insertion sorts are faster than bubble sorts.
Insertion sorts are useful to know about anyway. Not only will knowing how to implement an insertion sort give you another type of sort you can use, but it’s also one of the easier ones to learn. Once you’ve learned how to write an insertion sort, you will be one step closer to learning about more complex sorts like merge sorts.
How Do Insertion Sorts Work?
We’ve spoken enough about insertion sorts and their benefits. Let’s get down to business and sort an array using the insertion sort algorithm. Consider the following unsorted array:
In an insertion sort, the first element is considered sorted. The second element is stored in its own variable. We’ll call this variable
We need to compare
current_number with the item at the first position in the array. If
current_number is greater than the first element, it stays in the same place; otherwise, current_number is moved to the front of the first element.
4 is not greater than 9, so these two elements swap places.
The first two elements in our list are sorted. Next, we change the value of current_number to the third item in the list and compare it with all the items on its left.
Our current_number becomes 3. We need to compare:
- Is 3 greater than 9? No, so 3 is inserted before 9.
- Is 3 greater than 4? No, so 3 is moved before 4.
Our list now looks like this:
This process repeats until the list is sorted. Our list only has one more set of comparisons to perform because it only contains four values. In the next iteration, 5 becomes current_number.
- Is 5 greater than 9? No, so 5 moves before 9.
No more comparisons are made because 5 is the last number in our sorted list. After this iteration, our array has been sorted:
It’s that simple! In our insertion sort, we always kept the sorted values at the left of the list. The unsorted values appeared at the right.
For each iteration in the list, we compared current_number to all the unsorted items. This process repeated until our list was sorted.
How to Write a Python Insertion Sort
It’s all fine and well walking through the insertion sort on paper. Now it’s time to get into the nitty-gritty and implement an insertion sort in Python.
We’ll start by writing the function which performs our sort:
def sortNumbers(toSort): for number in range(1, len(toSort)): current_number = toSort[number] i = number - 1 while i >= 0 and current_number < toSort[i]: toSort[i + 1] = toSort[i] i -= 1 toSort[i + 1] = current_number
Let’s walk through how this works. In our
sortNumbers function we create a for loop which loops through every number in the list. Then, we set the first element in the list as a sorted value by assigning it to the variable
We then iterate through every item in the unsorted list (every item after current_number) and compare current_number with each element on its left.
After this happens, we set the value of
current_number as equal to the element after it in the list.
Next, we’ve got to write our main program which executes our insertion sort:
numbers = [9, 4, 3, 5] sortNumbers(numbers) print(numbers)
Our code returns: [3, 4, 5, 9]
Our list has been sorted in ascending order! Congratulations on getting this far.
Insertion sorts can be used to sort numbers in descending order. To accomplish this, you need to invert the “less than” (>) sign in the while loop and make it a greater than sign:
while i >= 0 and current_number > toSort[i]:
If you use this line of code, your list of numbers will be sorted in descending order.
Insertion sorts are like sorting a list of cards in your hand in a card game. You keep two lists: a list of sorted items and a list of items to sort. Then, you work your way through the list of unsorted items and shuffle their positions until they are all sorted.
Now you’re ready to start implementing an insertion sort in Python like an expert programmer!