Bubble Sort: Algorithm, Implementation, and Complexity
Bubble sort is the algorithm everyone learns first and uses never. That's not an insult—it's a recognition of its true purpose. This comparison-based sorting algorithm earned its name from the way...
Key Insights
- Bubble sort’s O(n²) time complexity makes it impractical for production use, but its simplicity makes it an excellent teaching tool for understanding sorting fundamentals and algorithm optimization.
- A single optimization—adding a “swapped” flag for early termination—transforms bubble sort’s best-case complexity from O(n²) to O(n), demonstrating how small changes can dramatically improve algorithm performance.
- Understanding why bubble sort is slow teaches you more about algorithm design than memorizing faster alternatives; the nested loop pattern and comparison-swap mechanism appear throughout computer science.
Introduction to Bubble Sort
Bubble sort is the algorithm everyone learns first and uses never. That’s not an insult—it’s a recognition of its true purpose. This comparison-based sorting algorithm earned its name from the way larger elements “bubble up” to the end of the array, like air bubbles rising through water.
The algorithm works by repeatedly stepping through a list, comparing adjacent elements, and swapping them if they’re in the wrong order. After each complete pass, the largest unsorted element finds its correct position at the end. The process repeats until no swaps are needed.
You’ll encounter bubble sort in three contexts: computer science courses, coding interviews (usually as a “what’s wrong with this approach” question), and occasionally when sorting very small datasets where code simplicity matters more than performance. Understanding bubble sort deeply will help you appreciate why more sophisticated algorithms exist and teach you fundamental concepts about algorithm optimization.
How the Algorithm Works
Let’s trace through bubble sort with a concrete example. Consider the array [5, 3, 8, 1, 2].
First pass:
- Compare 5 and 3: 5 > 3, swap →
[3, 5, 8, 1, 2] - Compare 5 and 8: 5 < 8, no swap →
[3, 5, 8, 1, 2] - Compare 8 and 1: 8 > 1, swap →
[3, 5, 1, 8, 2] - Compare 8 and 2: 8 > 2, swap →
[3, 5, 1, 2, 8]
After one pass, the largest element (8) has bubbled to its final position. We now have a sorted portion at the end and an unsorted portion at the beginning.
Second pass:
- Compare 3 and 5: no swap →
[3, 5, 1, 2, 8] - Compare 5 and 1: swap →
[3, 1, 5, 2, 8] - Compare 5 and 2: swap →
[3, 1, 2, 5, 8]
Now both 5 and 8 are in their final positions. The pattern continues until the entire array is sorted.
Here’s the logic in pseudocode:
procedure bubbleSort(array)
n = length(array)
for i from 0 to n-1
for j from 0 to n-i-2
if array[j] > array[j+1]
swap(array[j], array[j+1])
return array
The outer loop controls how many passes we make. The inner loop performs the actual comparisons and swaps. Notice n-i-2 in the inner loop bound—after each pass, we can ignore one more element at the end because it’s already sorted.
Basic Implementation
Let’s translate the pseudocode into working implementations. I’ll show both Python and JavaScript since they’re commonly used for learning algorithms.
def bubble_sort(arr):
"""
Basic bubble sort implementation.
Sorts the array in-place and returns it.
"""
n = len(arr)
# Outer loop: we need n-1 passes maximum
for i in range(n - 1):
# Inner loop: compare adjacent elements
# Range shrinks because last i elements are sorted
for j in range(n - 1 - i):
# If current element is greater than next, swap them
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))
# Output: [11, 12, 22, 25, 34, 64, 90]
function bubbleSort(arr) {
const n = arr.length;
// Outer loop: controls number of passes
for (let i = 0; i < n - 1; i++) {
// Inner loop: compare and swap adjacent elements
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap using destructuring
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
// Example usage
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(numbers));
// Output: [11, 12, 22, 25, 34, 64, 90]
Both implementations modify the array in-place, using O(1) extra space. The nested loops give us O(n²) comparisons regardless of the input’s initial state—even if the array is already sorted, we still perform every comparison.
Optimized Implementation
The basic implementation has a glaring inefficiency: it doesn’t recognize when the array becomes sorted early. If we complete a pass without making any swaps, the array is sorted and we can stop immediately.
def bubble_sort_optimized(arr):
"""
Optimized bubble sort with early termination.
Stops when no swaps occur in a pass.
"""
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no swaps occurred, array is sorted
if not swapped:
break
return arr
# Compare behavior on already-sorted array
already_sorted = [1, 2, 3, 4, 5]
# Basic version: still does all comparisons
# Optimized version: detects sorted state after one pass
function bubbleSortOptimized(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// Early termination if no swaps
if (!swapped) break;
}
return arr;
}
This single boolean flag transforms the best-case performance from O(n²) to O(n). On an already-sorted array, we make one pass, detect zero swaps, and exit. The worst case remains O(n²), but real-world data often has some existing order that this optimization exploits.
Time and Space Complexity Analysis
Understanding complexity requires examining three scenarios:
Worst Case: O(n²) Occurs when the array is reverse-sorted. Every element must bubble all the way to its position. For an array of n elements, we perform approximately n²/2 comparisons and n²/2 swaps.
# Worst case example
worst_case = [5, 4, 3, 2, 1]
# Element 1 must move 4 positions
# Element 2 must move 3 positions
# Total swaps: 4 + 3 + 2 + 1 = 10 = n(n-1)/2
Best Case: O(n) with optimization, O(n²) without An already-sorted array requires only one pass to verify no swaps are needed—if you implemented the swapped flag. Without it, you still perform all n² comparisons.
Average Case: O(n²) Random input requires, on average, n²/4 swaps. The quadratic nature dominates regardless of constants.
Space Complexity: O(1) Bubble sort is an in-place algorithm. We only need a few variables for loop counters and the swap operation, regardless of input size. This is one of bubble sort’s few advantages.
Comparison with Other Sorting Algorithms
Let’s put bubble sort’s performance in perspective with a practical benchmark:
import time
import random
def benchmark_sort(sort_func, arr):
"""Time a sorting function's execution."""
arr_copy = arr.copy()
start = time.perf_counter()
sort_func(arr_copy)
end = time.perf_counter()
return end - start
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Generate test data
sizes = [100, 500, 1000, 2000]
for size in sizes:
test_data = [random.randint(1, 10000) for _ in range(size)]
bubble_time = benchmark_sort(bubble_sort_optimized, test_data)
insertion_time = benchmark_sort(insertion_sort, test_data)
builtin_time = benchmark_sort(sorted, test_data)
print(f"Size {size}:")
print(f" Bubble sort: {bubble_time:.4f}s")
print(f" Insertion sort: {insertion_time:.4f}s")
print(f" Python sorted: {builtin_time:.6f}s")
Typical results show insertion sort outperforming bubble sort by 2-3x on random data, while Python’s built-in Timsort (O(n log n)) is orders of magnitude faster on larger inputs.
When to use what:
- Bubble sort: Teaching, arrays under 10 elements, or when code simplicity is paramount
- Insertion sort: Small arrays (under 50 elements), nearly-sorted data
- Quicksort/Mergesort: General-purpose sorting for larger datasets
- Built-in sorts: Production code—always use your language’s optimized implementation
Conclusion: Practical Takeaways
Bubble sort won’t appear in your production codebase, but the concepts it teaches are foundational. You’ve learned about in-place sorting (O(1) space), the power of a simple optimization flag, and why nested loops signal quadratic complexity.
The comparison-swap pattern appears throughout algorithms. The early termination optimization demonstrates a principle you’ll apply repeatedly: detect when work is complete and stop early. These insights transfer directly to more complex problems.
Use bubble sort to explain sorting to beginners, to verify your understanding of algorithm analysis, and as a baseline for appreciating efficient algorithms. Then reach for your language’s built-in sort function and move on to solving actual problems.