Bubble Sort

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;