DSA — Bubble Sort

What is Bubble Sort?

Repeatedly steps through the list, compares adjacent elements, and swaps them if wrong order.

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

Optimized Version

def bubble_sort_optimized(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]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Time Complexity

Case	Complexity
Best	O(n)
Average	O(n²)
Worst	O(n²)

Characteristics

• Stable sort
• In-place
• Simple to implement
• Inefficient for large datasets

Mini Practice

1. Implement bubble sort
2. Add optimization
3. Count comparisons and swaps
4. Sort in descending order

Up Next

Continue with Selection Sort — selection sorting algorithm.