Skip to content

BubbleSort

Jump to bottom
krishanthan4 edited this page Dec 16, 2025 · 1 revision

Bubble Sort

Problem Description

Implement bubble sort, a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.

What is Bubble Sort?

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. Larger elements "bubble up" to the end of the array.

Characteristics

  • Time Complexity:
    • Worst case: O(n²)
    • Average case: O(n²)
    • Best case: O(n) with optimization
  • Space Complexity: O(1) - sorts in place
  • Stability: Stable (preserves relative order of equal elements)
  • Adaptive: Can be optimized to detect if array is already sorted

How It Works

  1. Compare adjacent elements
  2. Swap them if they're in wrong order
  3. After each pass, the largest unsorted element reaches its correct position
  4. Repeat until no swaps are needed

Visual Example

Pass 1: [5, 2, 8, 1] → [2, 5, 8, 1] → [2, 5, 1, 8]
Pass 2: [2, 5, 1, 8] → [2, 1, 5, 8]
Pass 3: [2, 1, 5, 8] → [1, 2, 5, 8]

Your Task

Implement the following methods in BubbleSort.java:

  1. sort(int[] arr) - Basic bubble sort
  2. sortOptimized(int[] arr) - Optimized version with early termination

Test Cases to Consider

  • Already sorted array (best case for optimized version)
  • Reverse sorted array (worst case)
  • Array with duplicates
  • Single element array
  • Empty array
  • Random unsorted array

Hints

  • Use nested loops: outer loop for passes, inner loop for comparisons
  • After each pass, you can reduce the inner loop range by 1
  • For optimization: use a flag to detect if any swaps occurred in a pass
  • If no swaps in a pass, the array is sorted

Optimization Strategies

  1. Early termination: If no swaps in a pass, array is sorted
  2. Reduced range: After each pass, reduce inner loop by 1
  3. Cocktail sort: Alternate between forward and backward passes

Common Pitfalls

  • Off-by-one errors in loop bounds
  • Not reducing inner loop range (inefficient)
  • Swapping incorrectly

When to Use Bubble Sort

Use when:

  • Educational purposes (easy to understand)
  • Array is nearly sorted (with optimization)
  • Small datasets
  • Simplicity is more important than efficiency

Avoid when:

  • Large datasets (use QuickSort, MergeSort, or HeapSort)
  • Performance is critical

Follow-up Questions

  1. How would you modify bubble sort to sort in descending order?
  2. Can you implement a bidirectional bubble sort (Cocktail sort)?
  3. How many swaps does bubble sort make in the worst case?
  4. Is bubble sort stable? Why or why not?

Comparison with Other Sorts

Algorithm Time (Avg) Time (Worst) Space Stable
Bubble Sort O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(1) No
Insertion Sort O(n²) O(n²) O(1) Yes
Quick Sort O(n log n) O(n²) O(log n) No
Merge Sort O(n log n) O(n log n) O(n) Yes

Related Algorithms

  • Selection Sort
  • Insertion Sort
  • Cocktail Shaker Sort

Clone this wiki locally