After I first saw Data Structures and Algorithms in my college's curriculum, I revise them every year, and I try to do something innovative each time. I don't like to read the algorithms and start skimming them. Instead, I like to take one problem and try to solve it using these algorithms.
I was using
setTimeout in this code to pause the execution and wait for the animation to end and resolve the
Promise so that the user can easily understand what is going on inside the algorithm. And I personally believe that it benefits beginners if they see the things moving in front of them instead banging their heads to the wall after just reading the algorithms from the books (personal experience).
In this blog, I chose Bubble Sort because it is quite a simple algorithm and you can actually focus on the different parts of the problem rather than spending your valuable time to fixing the algorithm itself. It keeps us motivated and focused.
Let's start with the basic explanation of the bubble sort
Bubble sort algorithm works by repeatedly swapping the adjacent elements if they're not in the correct order.
Generally, we sort all the elements in their ascending order but if you want, you can sort them in descending order.
Let's put some facts about the Bubble Sort Algorithm
- Worst and Average Case Complexity: O (n^2).
The worst-case only occurs when an array is sorted in the reverse order.
- Best Case: O(n)
The best case occurs when an array is already sorted.
Auxiliary Space: O(1)
If you're thinking that
Auxiliary Space is
Space Complexity, you're highly mistaken.
Auxiliary Space is the temporary space used by an algorithm, while Space Complexity is the total space required by the algorithm which includes both the auxiliary space and the size of the input.
- If we use this algorithm to sort the data in ascending order, we'll get the maximum sorted value at the end of the first pass and the minimum value "after" the end of the last pass (because we're not sorting the last element).
What I learned from this?
Fix setTimeout and setInterval if the tab is inactive
If we use
setInterval and the tab in which our code is running is inactive, the rendering engine will only run that once per second.
I solved this using
window.requestAnimationFrame(). In the example above, if you switch to some other tab, it will stop this algorithm because I'm resolving a promise inside this
requestAnimationFrame function. It will continue sorting the algorithm once this tab is active.
Achieve upto 60fps animation speed
If you see the code closely, I'm not setting the vertical bars' position using
left or something. I'm setting it using the
transform property. Which helps improve the performance significantly by reducing the amount of effort the rendering engine has to put on.
I highly recommend you all to check this blog out to visually understand the difference in the performance using the dev tools.
What else you can do with this code?
I haven't put a lot of effort to create this, but yes you can change the number of bars and the speed of the animation.
If you have any idea to make things even better, don't keep it to yourself. Tell us in the comments. We wan't to know, don't be selfish.