What do we understand about Bubble Sort?
- It uses 2 for-loops
- outer loop loops DECREMENTALLY
- inner loop loops INCREMENTALLY
- it is also the loop that does the swapping
- The check for swap is simple
- it does the comparison in the inner loop
- it compares the current to 1 position next to the current
- bigger goes to the right, smaller or equals we skip
- Time complexity
- O(n^2)
- Space complexity
- O(1)
function BubbleSort(arr) {
for (let i = arr.length; i >= 0; i--) {
//! condition to check if we still proceed with the inner loop
let alreadySorted = true;
//! NOTE:
//! Since the previous loops already pushed the largest number to the right of the loop
//! the inner loop does not need to loop all the way to the end again.
for (let j = 0; i < i - 1; j++) {
//! compare left to right
if (arr[j] > arr[j + 1]) {
//! if nothing comes thru the if condition
//! means everything behind are already sorted
//! stop looping and break from the outer loop
alreadySorted = false;
//! SWAP
// this is the es6 syntax for swapping
// other languages may have the same
// I know Golang has something similar
[arr[j], arr[j+1]] = [arr[j+1], arr[ij];
}
}
if (alreadySorted) {
break;
}
}
//* return the result after all the loops have been done.
return arr;
}
NOTE: There is a way of writing the swap logic in a more universal way for most other languages to implement as well.
// a more universal swap logic
const temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
Top comments (0)