Understanding Bubble Sort Algorithm: A Step-by-Step Guide

#programming #datastructures #learning #javascript

Image Source: medium

Sorting is one of the most important parts of Data Structures and Algorithms. There are many types of sorting algorithms, and here is one of the easiest algorithms: Bubble sort.

Sorting algorithms are fundamental in computer science, and Bubble Sort is one of the simplest and most intuitive sorting algorithms. This post will explore how Bubble Sort works, analyze its time complexity, and walk through a JavaScript implementation.

In this series, I will share the complete Sorting Algorithm Data Structure and Algorithms using Javascript and start with Bubble Sort. If you like and want me to share the complete Sorting algorithm with an example, please like and follow me. It motivates me to create and prepare the content for you guys.

What is Bubble Sort?

Bubble Sort is an easy sorting algorithm that repeatedly steps through the list, compares adjacent elements (next elements), and swaps them if they are in the wrong order. This process is repeated until the list is sorted. The algorithm gets its name because smaller elements “bubble” to the top of the list.

JavaScript Implementation:

Let’s dive into the code to see how Bubble Sort is implemented in JavaScript:

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12];

Output

Sorting with Descding Orders:

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

Output:

Already added comments and explained each line of the code above. but I will also explain in detail so it helps you to understand the complete process and codes.

How it works:

Initialization: We start by determining the length of the array, which helps control the number of iterations.
Outer Loop: This loop runs n-1 times, where n is the length of the array. Each iteration ensures that the next largest element is placed in its correct position.
Inner Loop: For each pass of the outer loop, the inner loop compares adjacent elements and swaps them if they are out of order. The range of the inner loop decreases with each pass because the largest elements are already sorted at the end of the array.
Swapping: If an element is greater than the next one, they are swapped using a temporary variable.
Return: Finally, the sorted array is returned.

Optimized Version:

// optimized version:
function bubble_sort(array) {
    const len = array.length; // get the length of the array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop run n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value
        let isSwapped = false;
        for (let j = 0; j < len - i -1; j++) {
            //check if the first element is greater than the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSwapped =  true;
            }
        }

        //If no element swap by inner loop then break;
        if (isSwapped === false) {
            break;
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12];

Explanations:

for (let i = 0; i < len — 1; i++) This is the outer loop, which runs n-1 times, where n is the length of the array. The outer loop controls how many times the inner loop will execute. Each iteration of the outer loop ensures that the next largest element is placed in its correct position.
let isSwapped = false A boolean variable isSwapped is initialized to false. This variable is used to track whether any elements were swapped during the current pass of the inner loop. If no swaps occur, the array is already sorted, and the algorithm can terminate early.
for (let j = 0; j < len — i — 1; j++) { This is the inner loop, which iterates over the array elements up to len - i - 1. The - i part ensures that the loop does not consider the elements that have already been sorted in previous passes.
if (array[j] > array[j + 1]) { This condition checks if the current element is greater than the next element. If true, a swap is necessary to order the elements correctly.

let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSwapped = true;

These lines perform the swap of elements array[j] and array[j + 1] using a temporary variable temp. After the swap, isSwapped is set to true, indicating that a swap has occurred.

if (isSwapped === false) {
            break;
        }

After the inner loop completes, this condition checks if isSwapped is still false. If no swaps were made, the array is already sorted, and the outer loop can be exited early using break.
Finally, the sorted array is returned.

Time Complexity

The time complexity of Bubble Sort is (O(n²)) in the worst and average cases, where (n) is the number of elements in the array. This is because each element is compared with every other element. In the best case, when the array is already sorted, the time complexity can be (O(n)) if an optimization is added to stop the algorithm when no swaps are needed.

In the best-case scenario, when the array is already sorted, the algorithm can terminate early due to the isSwapped optimization, resulting in a time complexity of (O(n)).

Overall, bubble sorting is not efficient for large datasets due to its quadratic time complexity, but it can be useful for small arrays or as an educational tool to understand sorting algorithms.

Conclusion

Bubble Sort is an excellent algorithm for educational purposes due to its simplicity. However, it is not suitable for large datasets because of its quadratic time complexity. Despite its inefficiency, understanding Bubble Sort provides a foundation for learning more advanced sorting algorithms.