InsertionSort is a very popular and easy to learn sorting algorithm. In this article you will learn about the features of InsertionSort and how to implement the sorting algorithm in different programming languages. I will explain you the code and much more.
Enjoy reading!
Introduction
To explain you InsertionSort in a basic way, we will use a card example. Let’s imagine a deck of cards, where the cards have numbers from 1–10. We now want to sort the shuffled deck of cardes with the help of InsertionSort.
In one hand we have the already sorted cards and in the other hand we have the unsorted deck. We consider the first card of the unsorted deck as sorted, you will see why soon.
After doing this, we take the next card of the unsorted deck and place it in the right spot in the sorted deck. We repeat this, until our unsorted deck is empty.
https://www.geeksforgeeks.org/insertion-sort/ Everything starting from the green cards to the right is our “unsorted deck”, everything at the left is our “sorted deck”
Properties
Let’s begin with a very easy property. InsertionSort is a sorting algorithm that is stable. This means that if an array has two numbers that are the same, the sorting of the two numbers in relation to each other remains the same in a stable algorithm. In an unstable algorithm, this is not always the case.
https://simple.wikipedia.org/wiki/Stable_sorting_algorithm Stable vs Unstable Algorithm
Another very simple to understand property is the in-place execution. This means, that no matter how big the array is, we don’t need additional variables. So simply said: The additional space in the memory needed does not depend on how big the array is. InsertionSort is an in-place algorithm. The opposite property has MergeSort, it’s not an in-place algorithm. You can learn more about it here.
Let’s discuss the time complexity, and here it gets a little bit more complicated. Because I want to create an article, that is very beginner friendly, I won’t explain how the time complexity is calculated, but I will of course show you what the time complexity of InsertionSort is and what this means. If you want to know more about the math behind the time complexity of InsertionSort, I’ve found a great article explaining it here.
The best case of InsertionSort is O(n). This means, that needed time grows linear to the number of elements in the array (we call this n).
https://desmos.com/ Best Case Time complexity of InsertionSort simplified
The average case and worst case time complexity is the same, it’s O(n²). This means, that the needed time grows exponentially in connection to the elements in the array (n).
https://desmos.com/ Average- & Worst Case Time complexity of InsertionSort simplified
Efficiency in comparison to other sorting algorithms
InsertionSort is a kind of slow algorithm. But compared to BubbleSort (best-case: O(n), average & worst-case O(n²)). But now you are asking yourself, why is BubbleSort slower, if it has the same time-complexity? Well, because in O-Notation, we don’t look at the factor which stands before the n. We would now the factor if we would have done the calculations.
Now you are maybe thinking, wow, that’s nice, InsertionSort is very fast. Nah, it’s still a slow algorithm in comparision to sorting algorithms like MergeSort. MergeSort has a time complexity of O(n log n) and is way faster than InsertionSort.
https://desmos.com Comparision Average Case InsertionSort and MergeSort. Red: InsertionSort; Blue: MergeSort
Implementation of InsertionSort
Now we want to implement InsertionSort in different programming languages. I will first explain the general concept on how we will do this and then I will show you one implementation in python and one implementation in dart. I will also add some links for other programming languages like JavaScript.
Too implement InsertionSort into a programming language, you iterate through the array with a loop. In one interation you compare the the current element with the previous one. When the previous one is bigger than the current element we are looking at, both elements will be swapped. This will be repeated until the current element is at the right spot. So we can say, that the current element walks down the already sorted array until it’s in the right spot. This is also implemented in a loop, that counts down from the original position to one and stops, if no swap was done.
It’s important to mention, that with every iteration, the sorted area gets bigger by one element and the unsorted area gets smaller by one element.
Now we will look at the implementations. The first implementation I’ve wrote during in a “research paper” during 9th grade and the second one I’ve wrote for fun :).
Python implementation:
Implementation of InsertionSort in Python. Written by the author of this article.
Dart implementation:
Implementation of InsertionSort in Dart. Written by the author of this article.
If you need implementations for other languages, you can find some here (C++, C, Java, C#, PHP, Javascript)..,
Conclusion
In this post we have looked at how InsertionSort works and how you can implement the sorting algorithm in Dart & Python.
I hope you were able to learn something and enjoyed it! If so, I’d be very happy if you give this post some claps.
Oh, and before I forget to mention it: I’ll be introducing some more sorting algorithms in Dart and other languages in the near future. If you don’t want to miss that, you should definitely follow me!
Have a nice day and thank you very much for reading!