Bubble Sort

About

Bubble Sort works by repeatedly stepping through the array, comparing adjacent elements, and swapping them if they are in the wrong order. With each full pass through the data, the largest unsorted element "bubbles up" to its correct position at the end of the array, like bubbles rising to the surface of water.

![[BinarySort.mp4]]

Complexities

• Time complexity:
  • Best: $O(n)$
  • Average/Worst: $O(n^2)$
• Space complexity: $O(1)$

Code Implementation

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap if the current element is greater than the next
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                
        if not swapped:
            break
            
    return arr

Key Takeaways

• The "Early Stop" Optimization: Without the swapped flag tracker, Bubble Sort would run at $O(n^2)$ even if you gave it an already-sorted array. Always mention this optimization in interviews.
  
  

• In-Place & Stable: It uses zero extra memory and won't mess up the relative order of identical numbers.
  
  

• When to Use It: Practically never in production code. It is highly inefficient for large datasets. Its primary value is educational, as it teaches nested loops, boundary management, and sorting logic foundational to computer science.