Searching and Sorting Algorithms in Javascript — Part 2 (Bubble Sort).
Bubble sort is one of the simplest algorithms out there. It is very easy to implement (although, not all that glitters is Gold). The aim of any sorting algorithm is to arrange the items of a given list in a particular order, based on the relationship between the items of that list.
The way Bubble sort does this is by looping through the array multiple times and in each passing, push the biggest item towards the end of the array. Enough talks! Let’s see how this works!!
What does the algorithm look like?
Given an array of numbers, say [10, 8, 11, 1, 3, 80, 2, 7, 9], we want a function that will accept this array of numbers and return it to us “sorted”. So, we’ll except something like [1,2,3,7,8,9,10,11,80] to be returned back to us from the function.
The algorithm to do that can be seen below — (Forgive me if my algorithm looks a little bit confusing, don’t worry, you’ll understand properly when we start writing the actual code)
Let me try to explain further:
The way this algorithm works is by looping through your array over and over again (indefinitely, until all the items of your array have been sorted). On each loop, the function will do the following
- Take the element at the current index (i) and compare it to the element directly next to it (i + 1).
- If the element is greater (i.e arr[i] > arr[i +1], it swaps them and moves to the next number. If not, it moves to the next number without swapping.
3. The condition for this infinite loop to end is if, after a loop, no swap occurred at all. This means that all elements are now in their right position. At this point, we break the infinite loop and return the sorted array.
The code implementation of this algorithm can be found below:
I hope this explains how bubble sort works. If you still need more clarity on how it actually works, checkout this visual representation of the algorithm on visualgo — https://visualgo.net/en/sorting
Is that all?
Yes. That’s all. That’s all there’s is to know about the implementation of the bubble sort algorithm. However, in a case where you have a very large list, you don’t want to use a bubble sort algorithm. Why?
Remember when we talked about the Big O Notation in part 1 and then mentioned a gentleman called time complexity?
As explained in part 1, time complexity measures how fast the algorithm does what it does. In the case of the bubble sort algorithm, the time complexity is O(n**2) (Read as “O of n squared).
What all these gibberish means is that, bubble sort algorithm takes a very very long time to sort very large arrays (It tends to be slow when the length of the array increases). For large arrays, you might want to use more refined algorithms like Merge sort and quick sort.
See you on the next one — Selection Sort
