AV
LibraryBubble Sort

Bubble Sort

Easy

Bubble Sort is an elementary sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in wrong order. It is named because smaller elements "bubble" to the top of the list.

Time Complexity

O(n²)

Space Complexity

O(1)

Category

Sorting

Introduction to Bubble Sort

Bubble Sort is one of the simplest sorting algorithms, often used in introductory computer science courses. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

How It Works

The algorithm gets its name from the way the largest elements "bubble" to the end of the list after each pass. In each iteration:

1. Compare the first element with the second

2. If the first is greater, swap them

3. Move to the next pair and repeat

4. After each complete pass, the largest unsorted element is in its final position

Algorithm Complexity

**Time Complexity**: O(n²) - In the worst case, we need n passes, each comparing n elements
**Space Complexity**: O(1) - Only requires a constant amount of additional space for swapping

Best and Worst Cases

**Best Case**: O(n) - When the array is already sorted (with optimization)
**Worst Case**: O(n²) - When the array is reverse sorted
**Average Case**: O(n²) - For random data

Advantages

1. Simple to understand and implement

2. Requires no additional memory (in-place sorting)

3. Stable sorting algorithm (maintains relative order of equal elements)

4. Good for educational purposes

Disadvantages

1. Very inefficient for large datasets

2. Time complexity of O(n²) is poor compared to modern algorithms

3. Not adaptive - doesn't perform better on partially sorted data

4. Rarely used in practice due to better alternatives

When to Use

**Small datasets**: Effective for arrays with fewer than 50 elements
**Educational purposes**: Great for learning sorting concepts
**Nearly sorted data**: Can perform well with optimization
**Memory constraints**: When extra space is not available

Variations

1. **Optimized Bubble Sort**: Stop if no swaps occur in a pass

2. **Cocktail Shaker Sort**: Bubble sort in both directions

3. **Comb Sort**: Uses gap sequence instead of adjacent comparisons

Key Takeaways

  • Compares adjacent elements
  • Swaps if in wrong order
  • Largest element "bubbles" to end
  • Stable sorting algorithm
  • In-place sorting
  • Not suitable for large datasets

Implementation

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

Tags

sortingcomparisonsimplebeginner

Quick Stats

Difficulty:Easy
Type:Sorting

Share