If you’re new to the wild world of algorithms, bubble sort vs insertion sort may have you scratching your head…Or at least cursing your compiler.
So what’s the difference?
How do they work?
What makes each of these algorithms unique?
Bubble Sort vs Insertion Sort TLDR:
BUBBLE SORT: After i iterations the last i elements are the biggest and ordered. In each iteration, the bubble sort algorithm sifts through the unsorted section to find the maximum.
🧮 INSERTION SORT: After i iterations the first i elements are ordered. In each iteration the next element is bubbled through the sorted section until it reaches the proper location.
🧮 Simply stated? With bubble sort, the maximums are bubbled out of the unsorted section, whereas insertion sort elements are bubbled into the sorted section.
Let’s pop it off with bubble sort.
What is bubble sort?
Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
Watch the GIF:
For instance, the largest integer “bubbles” up to the top, or iterates its way to the end of the array through a comparison of each element.
Although bubble sort isn’t a very efficient algorithm (perhaps the worst!), it is still an important concept to understand.
Arguably, the only real perk the bubble sort has compared to other algorithms is its built-in ability to detect whether or not the array is sorted in the first place.
In a best case scenario, the list is already sorted or nearly sorted.
This is in contrast to other algorithms, even those with better than average performance, whose entire sorting process causes more inversions, reversals or swaps to happen.
An example of a bubble sort algorithm in Python:
Although bubble sort is one of the simplest sorting algorithms to understand and implement, its performance means that its efficiency decreases dramatically on arrays with larger amounts of elements.
And, it’s been argued that it shouldn’t be taught anymore as many consider it outdated and even hazardous to some CPUs – yikes!
I bet you didn’t realize you’d be entering dangerous territory here, now did you?
Who knew coding could be fraught with tenuous escapades such as this? How sexy!
But hey, if you thrive in a more stable and secure environment, let’s move on to insertion sort.
What is insertion sort?
Insertion sort is another simple sorting algorithm that builds the final array one item at a time.
Much like the bubble sort, it’s still inefficient on large lists but it can have some advantages including:
✅ simple implementation (meaning a reduced amount of lines of code)
✅ performs well with small data sets
✅ performs well with relatively sorted arrays
✅ doesn’t require much space (meaning it can be done “in-place” thus not using much computer memory in order to perform well)
With insertion sort, the idea is to “split” the array into two sections in order to compare its elements.
We can consider one side “sorted” (even with just one element) and the other side “unsorted”:
Our algorithm takes one element at a time from the unsorted side and compares it with our elements on the sorted side.
If our element is larger or smaller, it places it where it needs to be within our sorted side:
Each iteration takes an element from the unsorted side and places it into our sorted side all the way until there are no more elements to compare.
We are then left with a sorted array:
Bubble Sort vs Insertion Sort Conclusion
Bubble sort and insertion sort are both sorting algorithms.
However, with bubble sort, after i iterations the last i elements are the biggest and ordered. Then, in each iteration, the bubble sort algorithm sifts through the unsorted section to find the maximum. The maximums are bubbled out of the unsorted section.
On the other hand, with insertion sort, after i iterations the first i elements are ordered. In each iteration the next element is bubbled through the sorted section until it reaches the proper location.
Want to learn more about bubble sort vs insertion sort?
Check out this free 2-hour Introduction to Algorithms in Python course where this lesson continues!
You’ll code out a bubble sort algorithm, an insertion sort algorithm and much more.
Software engineers curious about Insertion Sort vs Bubble Sort are also reading: