Understanding bubble sort algorithm: Beginner's guide with leetcode problems

In the world of programming, sorting algorithms are fundamental. They're used in various applications, from organizing data in databases to optimizing search functions. Bubble Sort, with its straightforward approach, serves as a stepping stone to understanding more advanced sorting techniques.

Table of Contents

1. Introduction
2. What is Bubble Sort?
3. How does Bubble Sort work?
4. Time and Space Complexity
5. Implementing Bubble Sort
   • Basic Implementation
   • Optimized Implementation
6. Conclusion

Introduction

Bubble Sort is one of the simplest sorting algorithms, making it an excellent starting point for our journey in sorting techniques. While it may not be the most efficient for large datasets, understanding Bubble Sort lays a solid foundation for understanding more complex sorting algorithms.

What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Bubble sort sort elements basically by comparing each pair of elements in the array and swapping them if they are in the wrong order. It is an in-place sorting algorithm, meaning it sorts the elements within the array itself without needing additional memory.

The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each iteration, similar to air bubbles rising in a liquid.

How does Bubble Sort work?

Before we start writing code, let's walk through how Bubble Sort works using an example array: [5, 3, 8, 4, 2]. Assume we have this array [5, 3, 8, 4, 2] and we want to sort it in ascending order using Bubble Sort.

1. First pass:

• Compare 5 and 3: Swap → [3, 5, 8, 4, 2]
• Compare 5 and 8: No swap
• Compare 8 and 4: Swap → [3, 5, 4, 8, 2]
• Compare 8 and 2: Swap → [3, 5, 4, 2, 8]

1. Second pass:

• Compare 3 and 5: No swap
• Compare 5 and 4: Swap → [3, 4, 5, 2, 8]
• Compare 5 and 2: Swap → [3, 4, 2, 5, 8]
• Compare 5 and 8: No swap

1. Third pass:

• Compare 3 and 4: No swap
• Compare 4 and 2: Swap → [3, 2, 4, 5, 8]
• Compare 4 and 5: No swap
• Compare 5 and 8: No swap

1. Fourth pass:

• Compare 3 and 2: Swap → [2, 3, 4, 5, 8]
• Compare 3 and 4: No swap
• Compare 4 and 5: No swap
• Compare 5 and 8: No swap

1. Fifth pass:
   • No swaps needed, the array is sorted

After each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array. Notice how the number of total passes is 5 which is the length of the array but the last pass has no swap whatsoever, meaning if we had used 5 - 1 = 4 as the total number of passes, we'd have gotten the correct result. This is because the last element is already in its correct position after the fourth pass.

Time and Space Complexity of Bubble Sort

It is important to note that Bubble Sort is not the most efficient sorting algorithm for large datasets due to its quadratic time complexity O(n^2). However, it is still a good algorithm for small datasets or for educational purposes.

Time Complexity

The time complexity of Bubble Sort can be analyzed in three scenarios:

1. Worst-case scenario: O(n^2)

• This occurs when the array is in reverse order (meaning the array is already sorted in descending order and we want to sort it in ascending order), requiring the maximum number of swaps.
• For each of the n elements, we potentially need to do n-1 comparisons.

1. Best-case scenario: O(n)

• This occurs when the array is already sorted.
• With optimization (stopping early if no swaps are made), we only need to do one pass through the array.

1. Average-case scenario: O(n^2)
   • On average, we can expect quadratic time complexity.

Here, n represents the number of elements in the array.

Space Complexity

Bubble Sort has a space complexity of O(1), which means it uses constant extra space.

This is because Bubble Sort is an in-place sorting algorithm. It doesn't require any extra array or data structure for sorting. The swaps are done within the original array, using only a constant amount of extra memory for variables (like loop counters and temporary variables for swapping).

Implementation of Bubble Sort

We've seen how Bubble Sort works and how to analyze its time and space complexity, let's now implement it in JavaScript.

Here's a basic implementation of Bubble Sort in JavaScript:

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // <--- Outer loop runs n-1 times (O(n))
    for (let j = 0; j < n - i - 1; j++) {
      // <--- Inner loop runs n-1 times (O(n))
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray); // [64, 34, 25, 12, 22, 11, 90]
console.log("Sorted array:", bubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]

Let's break down the code:

1. The outer loop for (let i = 0; i < n - 1; i++) runs n-1 times, where n is the length of the array. This is because the last element is already in its correct position after the (n-1)th pass.
2. The inner loop for (let j = 0; j < n - i - 1; j++) compares adjacent elements (arr[j] and arr[j + 1]). Notice how the loop decreases as we progress through the array (i.e n - i - 1). This expression means that after you've looped through a number of elements from the first loop (i.e i from the outer loop), the number of comparisons decreases by i, so in our inner loop, we'd be comparing n - i - 1 elements not n - 1.
3. If an element is greater than the next one, they are swapped using destructuring assignment.
4. This process continues until no more swaps are needed.

Optimizing Bubble Sort

We can optimize Bubble Sort by adding a flag to check if any swaps were made in a pass. If no swaps were made, it means the array is already sorted, and we can stop the algorithm early.

Here's the optimized version:

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

  for (let i = 0; i < n - 1; i++) {
    swapped = false; // We initialize swapped to false

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true; // We set swapped to true to indicate that a swap occurred
      }
    }

    // If no swapping occurred, this means the array is sorted
    if (!swapped) break; // We break out of the loop if no swaps occurred
  }

  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray); // [64, 34, 25, 12, 22, 11, 90]
console.log("Sorted array:", optimizedBubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]

This optimization improves the best-case time complexity to O(n) when the array is already sorted or nearly sorted.

Solving LeetCode Bubble Sort Problems

Having studied how bubble sort works and how to implement it, let's solve some LeetCode problems using bubble sort to solidify our understanding.

Problem 1: Maximum Product of Two Elements in an Array [Easy]

Problem: Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Approach: This problem is a direct application of bubble sort. We can sort the array in ascending order and return the product of the last two elements, which are the two largest elements in the array.

Solution:

const maxProduct = function (nums) {
  // Implement bubble sort
  for (let i = 0; i < nums.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        // Swap elements
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
        swapped = true;
      }
    }
    // If no swapping occurred, array is sorted
    if (!swapped) break;
  }

  // Return the product of the last two elements (largest two)
  return (nums[nums.length - 1] - 1) * (nums[nums.length - 2] - 1);
};

Problem 2: Sort Colors [Medium]

Problem: Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.

Approach: We can use bubble sort to solve this problem efficiently. Since we only have three distinct values (0, 1, and 2), we can sort the array in-place using bubble sort. The algorithm will compare adjacent elements and swap them if they are in the wrong order. After each pass, the largest unsorted element will "bubble up" to its correct position. We'll repeat this process until the entire array is sorted, resulting in all red elements (0) at the beginning, followed by white elements (1), and then blue elements (2) at the end.

Solution:

const sortColors = function (nums) {
  var len = nums.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        // Swap nums[j] and nums[j + 1]
        var temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
      }
    }
  }
  return nums;
};

Conclusion

Bubble Sort is a simple and intuitive sorting algorithm that serves as an excellent introduction to the world of sorting techniques. Its simplicity makes it easy to understand and implement, making it a valuable learning tool for beginners.

Key points to remember about Bubble Sort:

1. It repeatedly steps through the list, comparing adjacent elements and swapping them if they're in the wrong order.
2. The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each iteration.
3. Time complexity: Worst and Average case O(n^2), Best case O(n) with optimization.
4. Space complexity: O(1) as it sorts in-place.
5. It can be optimized to stop early if the list becomes sorted before all passes are complete.

While Bubble Sort is not efficient for large datasets due to its quadratic time complexity O(n^2), understanding it provides a solid foundation for learning more advanced sorting algorithms. In practice, for larger datasets or performance-critical applications, more efficient algorithms like QuickSort, MergeSort, or built-in sorting functions are preferred.

In our next article, we'll be learning about another sorting algorithm called Selection Sort.

---

---

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

The Great SoluTion 🚀Follow

Software Engineer | Technical Writer | Backend, Web & Mobile Developer 💻 | Passionate about crafting efficient and scalable software solutions. #letsconnect 🤝

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding 👨‍💻🚀