Sorting Algorithms
Bubble sort is a simple and straightforward sorting algorithm that compares two adjacent elements in the list and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.
Interactive Bubble Sort Visualizer
Try the interactive visualizer below to see how bubble sort works step by step!
Interactive Bubble Sort Visualizer
How to use:
- Click Play to watch the bubble sort algorithm in action
- Adjust the speed slider to control animation speed
- Click Reset to return to the original array
- Colors indicate: Normal (blue), Comparing (yellow), Swapping (red), Sorted (green)
Time Complexity Analysis
Python Implementation Examples
📝 Basic Implementation
def bubble_sort_basic(arr):
"""Basic bubble sort - O(n²) for all cases"""
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]
result = bubble_sort_basic(numbers.copy())
print(result) # [11, 12, 22, 25, 34, 64, 90]⚡ Optimized with Early Termination
def bubble_sort_optimized(arr):
"""Optimized bubble sort with early termination"""
n = len(arr)
for i in range(n):
swapped = False
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
# Early termination if no swaps occurred
if not swapped:
break
return arr🔍 Explanation
The bubble_sort_basic function implements the basic bubble sort algorithm with a time complexity of O(n²) for all cases. The bubble_sort_optimized function adds an early termination condition to improve performance, especially for nearly sorted arrays.
Both functions take an array as input and return the sorted array. The optimized version checks if any swaps were made in each pass; if no swaps occur, it terminates early, indicating that the array is already sorted.