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)