Javascript Algorithms: Bubble Sort
Bubble sort is a sorting algorithm that can be use on relatively small data sets. In terms of big O notation, the best case scenario is O(n), in most cases however the run time will be O(n²). What bubble sort does is it compares every adjacent value to one another, if the current value is greater than the next value the two values swap positions. This continues on through multiple passes through the array until the larger values “bubble” to the end of the array.
To give a visual representation of this, lets say we have an array [3, 1, 2, 5, 4]
[3, 1, 2, 5, 4] → [1, 3, 2, 5, 4] → [1, 2, 3, 5, 4] → [1, 2, 3, 5, 4] → [1, 2, 3, 4, 5]
Get Kevin Lai’s stories in your inbox
Join Medium for free to get updates from this writer.
The bolded numbers represent the current pair of numbers being compared. In the first example 3 is greater than 1 so 3 and 1 swap places, the process continues through the fist pass and we find that we live in an ideal world our array is sorted. However lets look at another example with some code.
Our example here is [6, 2, 4, 3, 1], we want our end result to be [1, 2, 3, 4, 6]. We declare a variable length and set it equal to the length of the array. We open a for loop and nest another for loop inside, by doing this we are ensuring multiple passes over the array. In terms of efficiency, this method will loop over an already sorted array because we didn’t set conditions to stop the loop if the array is already sorted.
In this log above, we can see that by the fourth parent loop the array is sorted but the loop continues for a fifth and final iteration because our condition to stop is the length of the array.
In the code above we’ve refactored our code to be more efficient by adding in the additions of lines 7, 14, and 18. Before we enter our inner loop we declare a boolean named swap and set it equal to false, if a swap happens in the inner loop then we set swap to true, when we exit our inner loop we wrote a conditional that checks whether or not a swap has occurred if no swap has occurred then the loop breaks and we return our array.
You can see in the log above the iteration stops when the array has been sorted instead of continuing until the conditional for the loop has been met.










