Bubble Sort in Data Structure

Bubble Sort is one of the simplest sorting algorithms taught in data structures. It repeatedly compares adjacent elements in an array and swaps them if they are out of order, causing larger values to 'bubble up' toward the end of the array with each pass.

Dry Run Example

Sorting [5, 3, 8, 1]: Pass 1 compares (5,3)→swap, (5,8)→no swap, (8,1)→swap, giving [3, 5, 1, 8]. Pass 2 compares (3,5)→no swap, (5,1)→swap, giving [3, 1, 5, 8]. Pass 3 compares (3,1)→swap, giving the fully sorted [1, 3, 5, 8].

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Complexity

Where It Fits in DSA

• Commonly used as the first sorting algorithm taught due to its intuitive logic.
• Rarely used in production code due to poor performance on large datasets.
• Useful for teaching concepts like stability and in-place sorting.