Naive sort algorithms in JavaScript: Bubble sort
A naïve sort, also known as “brute force” or “generate and test,” is a sorting algorithm that generates all the possible permutations of a list, and then tests each permutation until one is found that is correctly sorted. The number of permutations of a list is n! (n factorial), where n is the length of the list. For a relatively small number of items such as 24, there are 6.20448E23 permutations. Due to the resource cost and time needed to generate and test the permutations of the list, programmers seldom use the naïve sort algorithm.
Quote source: www.chegg.com
What is bubble sort?
Bubble sort is an array sorting algorithm that compares neighboring values and swaps them accordingly until the array is sorted. So, if we had an array that equals to [5, 1, 4, 2, 8] on the first run it will compare “5” and “1” and since “5” is bigger than “1” it will swap them. Then it will compare “5” and “4” (since “5” is in the second location) and swap their places. The same continues for “5” and “2”. When it comes to “5” and “8” (5 is continuously carried from the first position since it’s bigger than all the elements) it compares them and since “8” is bigger than “5” no swap is needed here.
Since the array is still not sorted it will continue to compare values until it is.
It is better explained in the following step-by-step presentation:
We can see how the largest numbers begin to “bubble up” to the end of the list, henceforth the name.
Bubble sort with code
Review the following code:
This is a basic implementation that loops trough the array in quadratic time O(n²) no matter what. It doesn’t check if the array is already sorted in order to break from the loop.
A more optimized version:
I used ES6 destructuring assignment syntax for the swap helper function. The swap helper function in the basic solution will work fine if you’re not familiar with the syntax.
This is a more optimized version where the function will only loop until the array is sorted. When the array is sorted, the loop ends and the sorted array is returned.
Best case scenario for time complexity is O(n) — linear (when the array is already sorted). Worst case it’s quadratic time O(n²);
Testing for number of iterations:
Code copied from “A Practical Guide to Algorithms with JavaScript” by Bianca Gandolfo on frontendmasters.com
When we run this code we can see the following results:
From this test we can conclude the following:
In the BASIC implementation of the bubble sort algorithm, no matter how sorted the array is, it still goes trough the double loop so the time complexity is always O(n²) — quadratic.
In the OPTIMIZED implementation of the bubble sort algorithm the best case scenario is when the array is already sorted and the time complexity is O(n) — linear since it will only loop once trough the array and so it depends on the number of elements (n) in the array.
In the worst case scenario it will still loop trough in quadratic time O(n²).
How does the bubble sort stack up?
Time complexity: O(n²) — quadratic;
Space complexity: O(1) — constant — in place;
Internal / External: Internal;
Stability: Stable;
Recursive / Non-recursive: Non-recursive;
Comparison sort?: comparison;
Conclusions:
From the aforementioned we can conclude that the bubble sort time complexity is quadratic, or O(n²) in Big O notation. While the time complexity is sub-optimal, the space complexity is very favorable. This algorithm only needs a few pointers at a time in order to keep reference to the pairs it is looking at and swapping when needed. Since it is done in O(1) constant space, (it doesn’t create new arrays in memory, it just swaps values places) we can say that this is an in-place algorithm, which operates directly on the inputted data.
All the data for this algorithm is stored withing the main memory of the computer. This makes it an internal sort .This is vital to how bubble sort functions because as the algorithm processes data, it needs all of it to exist in one chunk. If this algorithm was external, it would result in even worse performance than it already has, as it would have to reference chunks of memory that could be potentially stored all over the place.
Bubble sort is a stable algorithm. It means that it preserves the relative order in sorted output as they appear in the input. If, lets say, we have an array of numbers and we have a couple of duplicate numbers. Ex: [3, 4, 4, 7, 5, 5] . When the array is sorted we have the following output [3, 4, 4, 5, 5, 7] . Because we only swap values by one index each loop, the duplicate entries preserve their order relative to their duplicates.
This algorithm doesn’t use recursion to sort arrays, instead it iterates trough the array and compares the values when needed. This makes it both non-recursive (iterative) and a comparison sort.
Here is a graph for a more visual representation of its time and space complexity:
As we can see, the time complexity is in the “Horrible” area and it’s space complexity is in the “Excellent” area.
Based on the aforementioned we can conclude that the bubble sort is pretty slow, makes a lot of comparisons and is sub-optimal. On the flip side it is rather easy to understand and might be come in handy if you have to code a quick sort algorithm for a small set of data. However, most of the time, it is not the case which means that we will want to avoid bubble sort. It is a fairy common interview question and it’s one of the reasons I’m learning it.
Resources
Bubble sort is an infamous algorithm, and you can find a lot of resources about it online. Here are a few:
- Bubble sort explained by Vaidehi Joshi — A much thorough guide than mine which I used as reference for this one with awesome illustrations to boot.
- HackerRank video — made by the author of Cracking the Coding Interview
- FrontEndMasters course for algorithms in JavaScript — Made by Bianca Gandolfo
Thank you for bearing with me until the end. I am a self-taught developer and this is written mostly for me to help me remember better and as a quick reference in case I need a reminder. If this article helped somebody else along the way then I’m all the more happier.
All constructive criticism is welcomed and encouraged.
