JavaScript Program to Implement the Bubble Sort Algorithm

Introduction

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. This guide will walk you through writing a JavaScript program to implement the Bubble Sort algorithm.

Problem Statement

Create a JavaScript program that:

• Sorts an array of integers using the Bubble Sort algorithm.
• Displays the sorted array.

Example:

• Input: [64, 34, 25, 12, 22, 11, 90]

• Output: [11, 12, 22, 25, 34, 64, 90]

• Input: [5, 1, 4, 2, 8]

• Output: [1, 2, 4, 5, 8]

Solution Steps

1. Initialize the Array: Provide an array of integers to be sorted.
2. Implement the Bubble Sort Logic:
   • Repeatedly compare adjacent elements.
   • Swap elements if they are in the wrong order.
   • Continue this process until no swaps are required (the array is sorted).
3. Display the Result: Output the sorted array.

JavaScript Program

// JavaScript Program to Implement Bubble Sort Algorithm
// Author: https://www.rameshfadatare.com/

// Step 1: Define the bubbleSort function
function bubbleSort(arr) {
    let n = arr.length;

    // Step 2: Outer loop to control the number of passes
    for (let i = 0; i < n - 1; i++) {
        // Step 3: Inner loop for comparison of adjacent elements
        for (let j = 0; j < n - 1 - i; j++) {
            // Step 4: Swap if the elements are in the wrong order
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

// Example usage
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("Original Array:", arr);
const sortedArray = bubbleSort(arr);
console.log("Sorted Array:", sortedArray);

Explanation

Step 1: Define the bubbleSort Function

• The bubbleSort function takes an array arr as input and returns the sorted array.

Step 2: Outer Loop to Control the Number of Passes

• The outer loop (for loop) runs n - 1 times, where n is the length of the array. This loop ensures that the array is passed over multiple times to ensure all elements are sorted.

Step 3: Inner Loop for Comparison of Adjacent Elements

• The inner loop compares adjacent elements of the array and performs the swaps when necessary. The n - 1 - i part ensures that we don't compare already sorted elements in the subsequent passes.

Step 4: Swap Elements if Necessary

• If the element on the left (arr[j]) is larger than the element on the right (arr[j + 1]), they are swapped. This is done using a temporary variable (temp).

Output Example

Original Array: [64, 34, 25, 12, 22, 11, 90]
Sorted Array: [11, 12, 22, 25, 34, 64, 90]

Example with Different Input

const arr = [5, 1, 4, 2, 8];
console.log("Original Array:", arr);
const sortedArray = bubbleSort(arr);
console.log("Sorted Array:", sortedArray);

Output:

Original Array: [5, 1, 4, 2, 8]
Sorted Array: [1, 2, 4, 5, 8]

Time Complexity

• Best Case: O(n) (with optimized version using a swapped flag).
• Worst Case: O(n²) (when the array is in reverse order).
• Average Case: O(n²).

Optimized Bubble Sort (Optional Improvement)

You can optimize the Bubble Sort by checking whether any swaps were made during the inner loop. If no swaps were made, the array is already sorted, and you can exit early.

Optimized Bubble Sort Program

function optimizedBubbleSort(arr) {
    let n = arr.length;
    let swapped;

    // Outer loop to control the number of passes
    for (let i = 0; i < n - 1; i++) {
        swapped = false;

        // Inner loop for comparison of adjacent elements
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }

        // If no elements were swapped, break out of the loop
        if (!swapped) {
            break;
        }
    }
    return arr;
}

// Example usage
const arr2 = [5, 1, 4, 2, 8];
console.log("Original Array:", arr2);
const sortedArray2 = optimizedBubbleSort(arr2);
console.log("Sorted Array (Optimized):", sortedArray2);

Output for Optimized Version

Original Array: [5, 1, 4, 2, 8]
Sorted Array (Optimized): [1, 2, 4, 5, 8]

Conclusion

This JavaScript program demonstrates how to implement the Bubble Sort algorithm by repeatedly swapping adjacent elements to sort the array. The optimized version includes a swapped flag to exit early if no swaps were made in a pass, reducing unnecessary iterations. This exercise is valuable for understanding basic sorting algorithms and improving efficiency through simple optimizations.