Bubble Sort
Master the simplest comparison-based sorting algorithm
š«§ What is Bubble Sort?
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The largest elements "bubble up" to the end of the array, like air bubbles rising to the surface.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
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]
sorted_numbers = bubble_sort(numbers.copy())
print(f"Sorted: {sorted_numbers}")
O(nĀ²)
Time Complexity
O(1)
Space Complexity
Stable
Sorting
Bubble Sort Characteristics
Simple
Easy to understand and implement
Beginner-friendly
Educational
In-Place
Sorts without extra memory
O(1) space
Memory efficient
Stable
Maintains relative order of equal elements
Preserves order
Predictable
Inefficient
Poor performance on large datasets
O(nĀ²) time
Not practical
Lesson 1: Basic Bubble Sort Implementation
Let's implement bubble sort step by step:
Bubble Sort Visualization
Initial: [64, 34, 25, 12, 22, 11, 90]
Pass 1: Compare adjacent elements, swap if needed
[34, 64, 25, 12, 22, 11, 90] ā 64 > 34, swap
[34, 25, 64, 12, 22, 11, 90] ā 64 > 25, swap
[34, 25, 12, 64, 22, 11, 90] ā 64 > 12, swap
[34, 25, 12, 22, 64, 11, 90] ā 64 > 22, swap
[34, 25, 12, 22, 11, 64, 90] ā 64 > 11, swap
[34, 25, 12, 22, 11, 64, 90] ā 64 < 90, no swap
Result: Largest element (90) is in correct position
Pass 2: Repeat for remaining elements
[25, 34, 12, 22, 11, 64, 90] ā Continue...
Final: [11, 12, 22, 25, 34, 64, 90]
Basic Bubble Sort
def bubble_sort(arr):
"""
Basic bubble sort implementation
"""
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n - i - 1):
# Swap if the element found is greater than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def bubble_sort_with_steps(arr):
"""Bubble sort with step-by-step visualization"""
arr = arr.copy() # Don't modify original
n = len(arr)
print(f"Initial array: {arr}")
for i in range(n):
print(f"\n--- Pass {i + 1} ---")
swapped = False
for j in range(0, n - i - 1):
print(f"Compare arr[{j}]={arr[j]} and arr[{j+1}]={arr[j+1]}")
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
print(f" Swapped! Array: {arr}")
else:
print(f" No swap needed")
print(f"After pass {i + 1}: {arr}")
if not swapped:
print("No swaps made, array is sorted!")
break
return arr
# Test bubble sort
test_array = [64, 34, 25, 12, 22, 11, 90]
print("=== Basic Bubble Sort ===")
result = bubble_sort(test_array.copy())
print(f"Sorted array: {result}")
print("\n=== Step-by-step Bubble Sort ===")
result = bubble_sort_with_steps(test_array)
Lesson 2: Optimized Bubble Sort
We can optimize bubble sort by detecting when the array is already sorted:
Optimized Bubble Sort
def bubble_sort_optimized(arr):
"""
Optimized bubble sort with early termination
"""
n = len(arr)
for i in range(n):
swapped = False
# Last i elements are already sorted
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no swapping occurred, array is sorted
if not swapped:
break
return arr
def bubble_sort_cocktail(arr):
"""
Cocktail sort (bidirectional bubble sort)
Sorts from both ends simultaneously
"""
n = len(arr)
start = 0
end = n - 1
swapped = True
while swapped:
swapped = False
# Forward pass (left to right)
for i in range(start, end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
if not swapped:
break
end -= 1
swapped = False
# Backward pass (right to left)
for i in range(end - 1, start - 1, -1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
start += 1
return arr
def count_comparisons_and_swaps(arr):
"""Count operations in bubble sort"""
arr = arr.copy()
n = len(arr)
comparisons = 0
swaps = 0
for i in range(n):
for j in range(0, n - i - 1):
comparisons += 1
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swaps += 1
return arr, comparisons, swaps
# Test optimizations
test_cases = [
[64, 34, 25, 12, 22, 11, 90], # Random
[1, 2, 3, 4, 5], # Already sorted
[5, 4, 3, 2, 1] # Reverse sorted
]
for i, test_arr in enumerate(test_cases):
print(f"\n=== Test Case {i + 1}: {test_arr} ===")
# Basic bubble sort
result, comps, swaps = count_comparisons_and_swaps(test_arr)
print(f"Basic: {comps} comparisons, {swaps} swaps")
# Optimized bubble sort
result_opt = bubble_sort_optimized(test_arr.copy())
print(f"Optimized result: {result_opt}")
# Cocktail sort
result_cocktail = bubble_sort_cocktail(test_arr.copy())
print(f"Cocktail result: {result_cocktail}")
Lesson 3: Bubble Sort Variations
Different variations for specific use cases:
Bubble Sort Variations
def bubble_sort_descending(arr):
"""Bubble sort in descending order"""
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] < arr[j + 1]: # Changed comparison
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def bubble_sort_custom_key(arr, key_func):
"""Bubble sort with custom comparison function"""
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if key_func(arr[j]) > key_func(arr[j + 1]):
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def bubble_sort_strings(arr, case_sensitive=True):
"""Bubble sort for strings"""
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
str1 = arr[j] if case_sensitive else arr[j].lower()
str2 = arr[j + 1] if case_sensitive else arr[j + 1].lower()
if str1 > str2:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def bubble_sort_objects(arr, attribute):
"""Bubble sort for objects by attribute"""
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if getattr(arr[j], attribute) > getattr(arr[j + 1], attribute):
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Test variations
print("=== Descending Order ===")
numbers = [64, 34, 25, 12, 22, 11, 90]
desc_result = bubble_sort_descending(numbers.copy())
print(f"Descending: {desc_result}")
print("\n=== Custom Key (by absolute value) ===")
mixed_numbers = [-5, 3, -1, 4, -2]
abs_result = bubble_sort_custom_key(mixed_numbers.copy(), abs)
print(f"By absolute value: {abs_result}")
print("\n=== String Sorting ===")
fruits = ["banana", "Apple", "cherry", "Date"]
case_sensitive = bubble_sort_strings(fruits.copy(), True)
case_insensitive = bubble_sort_strings(fruits.copy(), False)
print(f"Case sensitive: {case_sensitive}")
print(f"Case insensitive: {case_insensitive}")
print("\n=== Object Sorting ===")
class Student:
def __init__(self, name, grade):
self.name = name
self.grade = grade
def __repr__(self):
return f"{self.name}({self.grade})"
students = [
Student("Alice", 85),
Student("Bob", 92),
Student("Charlie", 78),
Student("Diana", 96)
]
sorted_students = bubble_sort_objects(students.copy(), 'grade')
print(f"Students by grade: {sorted_students}")
Lesson 4: Performance Analysis
Understanding bubble sort performance characteristics:
Performance Analysis
import time
import random
def analyze_bubble_sort_complexity():
"""Analyze time complexity of bubble sort"""
sizes = [100, 200, 500, 1000]
print("Bubble Sort Time Complexity Analysis")
print("=" * 50)
print(f"{'Size':<8} {'Best(ms)':<10} {'Average(ms)':<12} {'Worst(ms)':<10}")
print("-" * 50)
for size in sizes:
# Best case: already sorted
best_case = list(range(size))
start = time.time()
bubble_sort_optimized(best_case.copy())
best_time = (time.time() - start) * 1000
# Average case: random order
avg_times = []
for _ in range(5):
avg_case = [random.randint(1, size) for _ in range(size)]
start = time.time()
bubble_sort(avg_case.copy())
avg_times.append((time.time() - start) * 1000)
avg_time = sum(avg_times) / len(avg_times)
# Worst case: reverse sorted
worst_case = list(range(size, 0, -1))
start = time.time()
bubble_sort(worst_case.copy())
worst_time = (time.time() - start) * 1000
print(f"{size:<8} {best_time:<10.2f} {avg_time:<12.2f} {worst_time:<10.2f}")
def compare_sorting_algorithms():
"""Compare bubble sort with other algorithms"""
import random
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
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
sizes = [100, 500, 1000]
algorithms = [
("Bubble Sort", bubble_sort),
("Selection Sort", selection_sort),
("Insertion Sort", insertion_sort),
("Built-in Sort", sorted)
]
print("\nSorting Algorithm Comparison")
print("=" * 60)
for size in sizes:
print(f"\nArray size: {size}")
print("-" * 30)
test_data = [random.randint(1, 1000) for _ in range(size)]
for name, algorithm in algorithms:
start = time.time()
if name == "Built-in Sort":
result = algorithm(test_data)
else:
result = algorithm(test_data.copy())
end = time.time()
time_ms = (end - start) * 1000
print(f"{name:<15}: {time_ms:>8.2f} ms")
# Run performance analysis
analyze_bubble_sort_complexity()
compare_sorting_algorithms()
# Space complexity analysis
print("\n" + "=" * 50)
print("SPACE COMPLEXITY ANALYSIS")
print("=" * 50)
print("Bubble Sort: O(1) - In-place sorting")
print("- Only uses a constant amount of extra space")
print("- Swaps elements within the original array")
print("- No additional data structures needed")
print("- Memory usage doesn't grow with input size")
When to Use Bubble Sort
ā Good For
- Educational purposes
- Very small datasets (< 50 elements)
- Nearly sorted data
- Simple implementations
ā Avoid For
- Large datasets (> 100 elements)
- Performance-critical applications
- Production systems
- Real-time processing
šÆ Characteristics
- Stable sorting algorithm
- In-place sorting
- Simple to understand
- Adaptive (optimized version)
ā” Better Alternatives
- Quick Sort (O(n log n) average)
- Merge Sort (O(n log n) guaranteed)
- Insertion Sort (better for small arrays)
- Built-in sort functions