DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Updated on

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

Discussion (0)