Example 1 — Trace passes with early exit
Show the steps and the answer
Pass 1: 5 and 1 swap → [1, 5, 4, 2, 8]; 5 and 4 swap → [1, 4, 5, 2, 8]; 5 and 2 swap → [1, 4, 2, 5, 8]; 5 and 8 stay. 4 comparisons, 3 swaps.
The 5 travels right until it meets the larger 8. After this pass the largest value, 8, is certain to be in last place.
Pass 2, up to the 4th position: 1 and 4 stay; 4 and 2 swap → [1, 2, 4, 5, 8]; 4 and 5 stay. 3 comparisons, 1 swap.
The last position is already final, so this pass needs one comparison fewer.
Pass 3, up to the 3rd position: 1 and 2 stay; 2 and 4 stay. 2 comparisons, no swaps, so stop.
A pass with no swaps means every neighboring pair is in order, so the whole list is sorted.
Total: 4 + 3 + 2 = 9 comparisons and 3 + 1 = 4 swaps. Without the early exit, a 4th pass would add 1 more comparison, making 10.
The early exit saves every pass after the list is already in order.
Answer: [1, 2, 4, 5, 8] after 3 passes, with 9 comparisons and 4 swaps.
Takeaway: Shorten each pass by one position, and stop after the first pass that makes no swaps.