Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.
See all of my Google, Amazon, & Facebook interview study notes
Bubble Sort Overview
- Worst Complexity: n^2
- Average Complexity: n^2
- Best Complexity: n
- Space Complexity: 1
- Method: Exchanging
- Stable: Yes
- Class: Comparison Sort
Bubble Sort Notes
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Bubble Sort JS Implementation
const BubbleSort = (items = []) => {
for (let i = 0; i < items.length; i++)
{
for (let j = 0; j < items.length; j++)
{
if (items[j] > items[j + 1])
{
let temporary = items[j]
items[j] = items[j + 1]
items[j + 1] = temporary
}
}
}
return items
}
module.exports = BubbleSort
FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)
Top comments (3)
Best case of bubble sort [O(n)] would be linear given the array is already sorted and we only need to go through the items a single time. Far from the average case, but considering that wikipedia, the bigocheatsheet, and other notable references all include the "best case" sort of bubble sort as O(n) I added it in here as well.
bigocheatsheet.com/
en.wikipedia.org/wiki/Bubble_sort
The average and worst cases are both n^2.
The callback method was actually there for an experiment I did. It was an easy way for me to output something to the console for every operation executed utilizing bubble sort. I actually meant to remove that during this post (I copied the code snippet directly from my referenced github repo) so thanks for pointing that out so I can remove it.
Noted and appreciated Pavel.