Bubble Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Bubble Sort Algorithm

Start with unsorted array

↓

Compare adjacent elements

↓

If left > right?

Yes→Swap elements

↓

Move to next pair

↓

Reach end of array?

No→Repeat compare-swap

Yes↓

Array sorted, stop

Bubble Sort repeatedly compares pairs of adjacent elements and swaps them if they are in the wrong order, bubbling the largest unsorted element to the end each pass.

Execution Sample

DSA C++

int arr[] = {5, 3, 8, 1, 2};
int n = 5;
for (int i = 0; i < n-1; i++) {
  for (int j = 0; j < n-i-1; j++) {
    if (arr[j] > arr[j+1]) {
      std::swap(arr[j], arr[j+1]);
    }
  }
}

Sorts the array {5,3,8,1,2} using Bubble Sort by repeatedly swapping adjacent elements if out of order.

Execution Table

Step	Pass	Compare Indices	Compare Values	Swap?	Array State After Step
1	1	0 and 1	5 and 3	Yes	[3, 5, 8, 1, 2]
2	1	1 and 2	5 and 8	No	[3, 5, 8, 1, 2]
3	1	2 and 3	8 and 1	Yes	[3, 5, 1, 8, 2]
4	1	3 and 4	8 and 2	Yes	[3, 5, 1, 2, 8]
5	2	0 and 1	3 and 5	No	[3, 5, 1, 2, 8]
6	2	1 and 2	5 and 1	Yes	[3, 1, 5, 2, 8]
7	2	2 and 3	5 and 2	Yes	[3, 1, 2, 5, 8]
8	3	0 and 1	3 and 1	Yes	[1, 3, 2, 5, 8]
9	3	1 and 2	3 and 2	Yes	[1, 2, 3, 5, 8]
10	4	0 and 1	1 and 2	No	[1, 2, 3, 5, 8]

💡 No swaps needed in last pass, array is sorted.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 9	Final
arr	[5, 3, 8, 1, 2]	[3, 5, 1, 2, 8]	[3, 1, 2, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]
i (pass)	0	0	1	2	4
j (compare index)	0	3	2	1	0

Key Moments - 3 Insights

Why do we stop inner loop at n - i - 1 instead of n - 1?

Because after each pass i, the last i elements are already sorted and in place, so we don't need to compare them again. See execution_table rows where pass increases and inner loop range decreases.

Why do we swap only when left element is greater than right?

Swapping only when left > right ensures the larger elements move towards the end, sorting the array in ascending order. This is shown in execution_table rows where swaps happen only if arr[j] > arr[j+1].

What happens if the array is already sorted?

If the array is sorted, no swaps occur during a pass, so the algorithm can stop early. In this example, the last pass (pass 4) has no swaps, so sorting ends.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 4?

A [3, 5, 1, 2, 8]

B [5, 3, 8, 1, 2]

C [3, 1, 2, 5, 8]

D [1, 2, 3, 5, 8]

💡 Hint

Check the 'Array State After Step' column in execution_table row with Step 4.

At which step does the first swap happen in pass 3?

A Step 6

B Step 8

C Step 5

D Step 9

💡 Hint

Look for pass 3 in execution_table and find the first 'Yes' in Swap? column.

If we change the array to already sorted [1, 2, 3, 5, 8], how would the swaps change?

A Swaps only in first pass

B Swaps in every pass

C No swaps at all

D Swaps only in last pass

💡 Hint

Refer to key_moments about what happens if array is already sorted.

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left > right
- Largest unsorted element moves to end each pass
- Inner loop runs n - i - 1 times per pass
- Stops early if no swaps in a pass

Full Transcript

Bubble Sort works by comparing pairs of adjacent elements in an array. If the left element is bigger than the right, they swap places. This process repeats for each pair in the array, pushing the largest unsorted element to the end. Each pass reduces the number of elements to check because the end elements become sorted. The algorithm stops when a pass completes with no swaps, meaning the array is sorted. The example array {5,3,8,1,2} is sorted step-by-step, showing swaps and array states after each comparison.