Bubble Sort

Idea

Bubble Sort repeatedly compares adjacent elements and “bubbles” the larger (or smaller) one toward the end, pass by pass, until fully sorted.

Algorithm

1. Scan adjacent pairs; swap if out of order.
2. Each pass bubbles the max (or min) of the unsorted part to the end.
3. Repeat for $n-1$ passes until sorted.

Pseudo-code:

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if A[j] > A[j+1]:
            swap(A[j], A[j+1])

Complexity

• Best: $O(n)$ (already sorted, with early-exit optimization)
• Worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: stable

Exercises

Exercise 1

Sort $A = [4, 3, 2, 1]$ with bubble sort; show each pass.

Exercise 2

What are the time and space complexities of bubble sort?