Algorithms: Bubble Sort
Lets start with the basic och algorithms. We have a algorithm called Bubble Sort. This algorithm works in the following manor. When going through an array of elements it will swap the values if they are in the wrong order. It is called bubble sort because of the process "bubbles" refers to the largest (or smallest) elements to the top or bottom of the list. It can be seen as bubbles rising to the surface in water.
So if we have an array of numbers [1, 5, 2, 6, 5, 9, 10] it will compare the first adjacent items. If the first element is larger than the second (for ascending order) it will swap them to the correct position. And then it will go to the next item in the list and continue until it has gone through all the items in the list.
Lets put this in context of Big O complexity to see what is going on here. If you want a brief refresher about the different types of Time complexity just read my post about this here 👇.
If we have a sorted list already and are running bubble sort on the sorted array we get in best case a time complexity of O(n).
If a list is in reverse order we can see that the worst case time complexity will be O(n^2).
When talking about space complexity we get a O(1) since it is a in-place sorting algorithm.
Lets look at some examples in node js to demonstrate different time complexities.
Here we have the most optimised example where we already have an sorted array to begin with. As we described before with the already sorted algorithm for Bubble Sort we get O(n).
Lets continue with an average case where we have an array that is in random order and Bubble sort need to actually do multiple swaps.
With this approach when having a array with random numbers we need to do multiple swaps in order to sort the full array. In this approach we get O(n^2).
Lets continue with the most extreme condition of Bubble sort. That is when working with arrays in reverse order. This approach will cause the maximum number of swaps and iterations.
Since we need to go through the array in reverse order and the maximum number of iterations and swaps we get a time complexity of O(n^2)
Key Takeaways
- Since Bubble sort is so inefficient is mostly used for education purposes and not used in real life applications.
- If used in real life problems is is mostly used for a very small datasets
| Case | Time Complexity | Description |
|---|---|---|
| Best Case | Already sorted, early termination. | |
| Average Case | Random order, multiple swaps needed. | |
| Worst Case | Reverse order, maximum swaps. |
If you are interesting in following along my journey I have a public repository where I provide all the node js examples of the algorithms below.
So now when we understand the basics of Bubble sort and the complexity that comes with it we must practice this together.
Here is some basic -> Expert exercises for Bubble Sort
Andreas Jangefalk