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

Image source: medium

Sorting is one of the most important parts of data structures and algorithms. There are many sorting algorithms, and here is one of the simplest: bubble sort.

Sorting algorithms are the foundation of computer science, and bubble sort is one of the simplest and most intuitive sorting algorithms. This article will explore how bubble sort works, analyze its time complexity, and introduce the JavaScript implementation step by step.

In this series, I will share the complete sort algorithm data structure and algorithm using Javascript, starting with bubble sort. If you like and want me to share the complete sorting algorithm through examples, please like and follow me. It inspires me to create and prepare content for you.

What is bubble sort?

Bubble sort is a simple sorting algorithm that repeatedly traverses a list, comparing adjacent elements (the next element) and swapping them if they are in the wrong order. Repeat this process until the list is sorted. The algorithm gets its name because smaller elements “bubble” to the top of the list.

JavaScript implementation:

Let’s dig 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

Sort in descending order:

// 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:

Each line of code above has been commented and explained. But I will also explain it in detail to help you understand the complete process and code.

How it works:

• Initialization: We first determine 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 the correct position.
• Inner Loop: For each iteration 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 element is already sorted at the end of the array.
• Swap: If one element is larger than the next, swap them using temporary variables.
• Return: Finally return the sorted array.

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]; 

illustrate:

• for (let i = 0; i < len — 1; i++)

  This is the outer loop, run n-1 time, place n is the length of the array. The outer loop controls the number of times the inner loop is executed. Each iteration of the outer loop ensures that the next largest element is placed in the correct location.

• let isSwapped = false

  The Boolean variable isSwapped is initialized to false. This variable is used to track whether any elements were exchanged during the current pass of the inner loop. If no swap occurs, 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 until len - i - 1. this - i Partially ensures that the loop does not consider elements that were already 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, swapping is required to order the elements correctly.

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

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

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

• After the inner loop completes, this condition checks whether isSwapped is still false. If no swapping occurs, the array is already sorted and break can be used to exit the outer loop early.
• 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 every element is compared to every other element. In the best case, when the array is already sorted, the time complexity can be (O(n)) If you add an optimization to stop the algorithm when swapping is not needed.

In the best case, 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 sort is not efficient for large datasets due to its quadratic time complexity, but can be useful for small arrays or as an educational tool for understanding sorting algorithms.

in conclusion

Due to its simplicity, bubble sort is an excellent algorithm for educational purposes. However, due to its quadratic time complexity, it is not suitable for large datasets. Although bubble sort is inefficient, understanding bubble sort lays the foundation for learning more advanced sorting algorithms.