Implement the Bubble Sort algorithm in Dart. Explain its time complexity in best, average, and worst cases. When would you use it in production?

Overview

Bubble Sort is 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. The algorithm gets its name because smaller elements "bubble" to the top (beginning) of the list with each pass.

While not efficient for large datasets, Bubble Sort is important for understanding sorting fundamentals, algorithm optimization, and serves as a baseline for comparing more advanced algorithms. It's also one of the few sorting algorithms that can detect if a list is already sorted in a single pass.

Key characteristics:

• Simple to understand and implement
• In-place sorting (no extra memory needed)
• Stable sort (preserves order of equal elements)
• Adaptive (efficient for nearly sorted data when optimized)

Algorithm Explanation

How Bubble Sort Works:

1. Start at the beginning of the array
2. Compare each pair of adjacent elements
3. Swap them if they're in wrong order (left > right for ascending)
4. After first pass, largest element is at the end
5. Repeat for remaining unsorted portion
6. Continue until no swaps occur (list is sorted)

Visual Example:

textCopy
Initial: [5, 2, 8, 1, 9]

Pass 1: [2, 5, 1, 8, 9]  → 9 bubbles to end
Pass 2: [2, 1, 5, 8, 9]  → 8 in position
Pass 3: [1, 2, 5, 8, 9]  → 5 in position
Pass 4: [1, 2, 5, 8, 9]  → No swaps, done!

Approach 1: Basic Implementation

The straightforward implementation without optimization.

dartCopy
List<int> bubbleSort(List<int> arr) {
  int n = arr.length;

  // Outer loop for number of passes
  for (int i = 0; i < n - 1; i++) {
    // Inner loop for comparisons in each pass
    for (int j = 0; j < n - i - 1; j++) {
      // Swap if current element > next element
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];
  print('Before: $numbers');

  bubbleSort(numbers);
  print('After: $numbers');
  // Output: [11, 12, 22, 25, 34, 64, 90]
}

Time Complexity:

• Best Case: O(n²) - still checks all pairs
• Average Case: O(n²)
• Worst Case: O(n²)

Space Complexity: O(1) - sorts in place

Problem: Always performs n² comparisons, even if already sorted!

Approach 2: Optimized with Early Exit

Add a flag to detect when list becomes sorted.

dartCopy
List<int> bubbleSortOptimized(List<int> arr) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    bool swapped = false;  // Track if any swap occurred

    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }

    // If no swaps, array is sorted
    if (!swapped) {
      break;
    }
  }

  return arr;
}

void main() {
  // Already sorted - exits after 1 pass!
  List<int> sorted = [1, 2, 3, 4, 5];
  bubbleSortOptimized(sorted);

  // Nearly sorted - faster than basic
  List<int> nearlySorted = [1, 2, 4, 3, 5];
  bubbleSortOptimized(nearlySorted);
}

Time Complexity:

• Best Case: O(n) - already sorted, one pass only!
• Average Case: O(n²)
• Worst Case: O(n²) - reverse sorted

Space Complexity: O(1)

Improvement: Detects sorted arrays early, making it adaptive.

Approach 3: Descending Order

Sort in descending order by reversing comparison.

dartCopy
List<int> bubbleSortDescending(List<int> arr) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    bool swapped = false;

    for (int j = 0; j < n - i - 1; j++) {
      // Swap if current < next (opposite of ascending)
      if (arr[j] < arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return arr;
}

void main() {
  List<int> numbers = [5, 2, 8, 1, 9];
  bubbleSortDescending(numbers);
  print(numbers);  // [9, 8, 5, 2, 1]
}

Approach 4: Generic Sorting with Comparator

Sort any type using a custom comparator function.

dartCopy
void bubbleSortGeneric<T>(
  List<T> arr,
  int Function(T a, T b) compare
) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    bool swapped = false;

    for (int j = 0; j < n - i - 1; j++) {
      // Use comparator: positive if a > b
      if (compare(arr[j], arr[j + 1]) > 0) {
        T temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }

    if (!swapped) break;
  }
}

void main() {
  // Sort integers
  List<int> numbers = [5, 2, 8];
  bubbleSortGeneric(numbers, (a, b) => a.compareTo(b));
  print(numbers);  // [2, 5, 8]

  // Sort strings by length
  List<String> words = ['apple', 'pie', 'banana'];
  bubbleSortGeneric(words, (a, b) => a.length.compareTo(b.length));
  print(words);  // [pie, apple, banana]

  // Sort custom objects
  List<Person> people = [
    Person('Alice', 30),
    Person('Bob', 25),
    Person('Charlie', 35),
  ];
  bubbleSortGeneric(people, (a, b) => a.age.compareTo(b.age));
  print(people.map((p) => p.name).toList());  // [Bob, Alice, Charlie]
}

class Person {
  final String name;
  final int age;
  Person(this.name, this.age);
}

Complete Solution Class

Production-ready implementation with all features.

dartCopy
class BubbleSort {
  /// Basic bubble sort - O(n²) always
  static void sort(List<int> arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          _swap(arr, j, j + 1);
        }
      }
    }
  }

  /// Optimized with early exit - O(n) best case
  static void sortOptimized(List<int> arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      bool swapped = false;
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          _swap(arr, j, j + 1);
          swapped = true;
        }
      }
      if (!swapped) break;
    }
  }

  /// Generic sort with comparator
  static void sortGeneric<T>(
    List<T> arr,
    int Function(T a, T b) compare,
  ) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      bool swapped = false;
      for (int j = 0; j < n - i - 1; j++) {
        if (compare(arr[j], arr[j + 1]) > 0) {
          _swapGeneric(arr, j, j + 1);
          swapped = true;
        }
      }
      if (!swapped) break;
    }
  }

  /// Sort with step-by-step tracking (educational)
  static List<List<int>> sortWithSteps(List<int> arr) {
    List<List<int>> steps = [List.from(arr)];
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
      bool swapped = false;
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          _swap(arr, j, j + 1);
          steps.add(List.from(arr));
          swapped = true;
        }
      }
      if (!swapped) break;
    }

    return steps;
  }

  static void _swap(List<int> arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  static void _swapGeneric<T>(List<T> arr, int i, int j) {
    T temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Comparison Table

Visualization Example

Step-by-step execution for

[5, 2, 8, 1, 9]

dartCopy
void visualize() {
  List<int> arr = [5, 2, 8, 1, 9];
  List<List<int>> steps = BubbleSort.sortWithSteps(arr);

  for (int i = 0; i < steps.length; i++) {
    print('Step $i: ${steps[i]}');
  }
}

// Output:
// Step 0: [5, 2, 8, 1, 9]  ← Initial
// Step 1: [2, 5, 8, 1, 9]  ← Swap 5,2
// Step 2: [2, 5, 1, 8, 9]  ← Swap 8,1
// Step 3: [2, 1, 5, 8, 9]  ← Swap 5,1
// Step 4: [1, 2, 5, 8, 9]  ← Swap 2,1

Pass breakdown:

• Pass 1: 4 comparisons, 9 bubbles to end
• Pass 2: 3 comparisons, 8 in position
• Pass 3: 2 comparisons, 5 in position
• Pass 4: 1 comparison, 2 in position
• Total: 10 comparisons, 4 swaps

Edge Cases

dartCopy
void testEdgeCases() {
  // Empty array
  List<int> empty = [];
  BubbleSort.sort(empty);
  assert(empty.isEmpty);

  // Single element
  List<int> single = [42];
  BubbleSort.sort(single);
  assert(single == [42]);

  // Two elements
  List<int> two = [2, 1];
  BubbleSort.sort(two);
  assert(two == [1, 2]);

  // Already sorted
  List<int> sorted = [1, 2, 3, 4, 5];
  BubbleSort.sortOptimized(sorted);
  assert(sorted == [1, 2, 3, 4, 5]);

  // Reverse sorted (worst case)
  List<int> reverse = [5, 4, 3, 2, 1];
  BubbleSort.sort(reverse);
  assert(reverse == [1, 2, 3, 4, 5]);

  // Duplicates
  List<int> duplicates = [3, 1, 2, 1, 3];
  BubbleSort.sort(duplicates);
  assert(duplicates == [1, 1, 2, 3, 3]);

  // All same
  List<int> same = [5, 5, 5, 5];
  BubbleSort.sort(same);
  assert(same == [5, 5, 5, 5]);
}

Best Practices

1. Always Use Optimized Version

dartCopy
// ✅ Good - exits early if sorted
BubbleSort.sortOptimized(arr);

// ❌ Bad - always does O(n²) work
BubbleSort.sort(arr);

2. Know When NOT to Use

dartCopy
// ❌ Never in production for large datasets
List<int> huge = List.generate(10000, (i) => Random().nextInt(10000));
BubbleSort.sort(huge);  // Takes seconds!

// ✅ Use Dart's built-in sort (TimSort)
huge.sort();  // Milliseconds!

3. Appropriate Use Cases

dartCopy
// ✅ Good - small list (< 10 elements)
List<int> small = [5, 2, 8];
BubbleSort.sortOptimized(small);

// ✅ Good - nearly sorted data
List<int> nearlySorted = [1, 2, 4, 3, 5];  // Only one swap needed
BubbleSort.sortOptimized(nearlySorted);  // O(n) performance!

// ✅ Good - educational purposes
void teachSorting() {
  var steps = BubbleSort.sortWithSteps([5, 2, 8, 1]);
  // Show visualization to students
}

4. Prefer Built-in for Production

dartCopy
// ❌ Don't write custom sorting unless required
void sortUserData(List<User> users) {
  bubbleSortGeneric(users, (a, b) => a.name.compareTo(b.name));
}

// ✅ Use Dart's optimized sort
void sortUserData(List<User> users) {
  users.sort((a, b) => a.name.compareTo(b.name));
}

Interview Tips

Common Interview Questions:

Q: "What's the time complexity of bubble sort?"

• Best: O(n) with optimization and already sorted data
• Average/Worst: O(n²)
• Always mention the optimization flag!

Q: "Is bubble sort stable?"

• Yes! Equal elements maintain their relative order
• Stability matters for multi-key sorting

Q: "When would you use bubble sort?"

• Educational purposes (learning algorithms)
• Very small datasets (< 10 elements)
• Nearly sorted data with optimization
• When O(1) space is critical
• Never for large production datasets

Q: "How can you optimize bubble sort?"

• Add early exit flag (O(n) best case)
• Track last swap position (reduce inner loop)
• Bidirectional bubble sort (cocktail sort)
• But ultimately, switch to O(n log n) algorithms!

Follow-up Questions:

• "Compare with insertion sort" → Both O(n²), insertion better in practice
• "Why is it called bubble sort?" → Elements bubble up like bubbles
• "Is it in-place?" → Yes, O(1) space
• "Can you make it recursive?" → Possible but adds O(n) space overhead

Red Flags to Avoid:

• Saying "bubble sort is good for production" ❌
• Not mentioning the optimization ❌
• Claiming it's O(n log n) ❌
• Not knowing when to use better algorithms ❌

Resources

• Bubble Sort - Wikipedia
• Sorting Algorithms - Dart
• Visualizing Bubble Sort