Bubble Sort

Bubble sort compares adjacent pairs of elements and swaps them if they are in the wrong order. It repeats this process across multiple passes through the list until no more swaps are needed and the list is fully sorted.

The name comes from the effect each pass has: the largest unsorted element gradually "bubbles up" to its correct position at the end of the list.

After each pass, the next-largest unsorted element settles into its final position. After k passes, the k largest elements are in their correct positions at the end.

Rules for each comparison:

• Compare the element at position $i$ with the element at position $i+1$
• If they are in the wrong order (left > right), swap them
• Move on to the next pair
• Repeat until the end of the unsorted region

For a list of $n$ elements, at most $n-1$ passes are needed.

Sort [5, 3, 8, 1, 4] using bubble sort.

Starting with the full list, pass 1 makes $n-1=4$ comparisons:

Step	Comparison	Swap?	List after step
1	5 vs 3	Yes	[3, 5, 8, 1, 4]
2	5 vs 8	No	[3, 5, 8, 1, 4]
3	8 vs 1	Yes	[3, 5, 1, 8, 4]
4	8 vs 4	Yes	[3, 5, 1, 4, 8]

After pass 1: [3, 5, 1, 4, 8]

The value 8 — the largest element — has reached its final position at the end. It will not be compared again in future passes.

Write carries and swaps explicitly in exams. Do not attempt to track multiple swaps mentally.

Continuing with [3, 5, 1, 4, 8]. Each pass shortens the unsorted region by one element.

Pass 2 (3 comparisons — position 4 is already sorted):

Step	Comparison	Swap?	List after step
1	3 vs 5	No	[3, 5, 1, 4, 8]
2	5 vs 1	Yes	[3, 1, 5, 4, 8]
3	5 vs 4	Yes	[3, 1, 4, 5, 8]

Remaining passes (summary):

After pass	List state	Sorted region
1	[3, 5, 1, 4, 8]	last 1 element
2	[3, 1, 4, 5, 8]	last 2 elements
3	[1, 3, 4, 5, 8]	last 3 elements
4	[1, 3, 4, 5, 8]	fully sorted

Pass 3 details: compare 3 vs 1 (swap → [1, 3, 4, 5, 8]), compare 3 vs 4 (no swap). Pass 4: compare 1 vs 3 (no swap). List is now sorted.