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.

Practice

1. What is the main idea behind the Bubble Sort algorithm?

easy

A. Divide the array into halves and sort each half separately

B. Repeatedly swap adjacent elements if they are in the wrong order

C. Select the smallest element and move it to the beginning

D. Insert each element into its correct position in a sorted part

Solution

1. Step 1: Understand Bubble Sort process

   Bubble Sort compares adjacent elements and swaps them if they are out of order.

2. Step 2: Identify the correct description

   This swapping of neighbors repeats until the whole list is sorted.

3. Final Answer:

   Repeatedly swap adjacent elements if they are in the wrong order -> Option B

4. Quick Check:

   Bubble Sort = Swap neighbors repeatedly [OK]

Hint: Bubble Sort swaps neighbors repeatedly until sorted [OK]

Common Mistakes:

• Confusing Bubble Sort with Selection Sort
• Thinking it divides the array like Merge Sort
• Assuming it inserts elements like Insertion Sort

2. Which of the following is the correct syntax for the inner loop of Bubble Sort in C++ to compare adjacent elements in an array arr of size n?

easy

A. for (int j = 0; j < n - i - 1; j++)

B. for (int j = 0; j < n; j++)

C. for (int j = 1; j < n - i; j++)

D. for (int j = 0; j <= n - i; j++)

Solution

1. Step 1: Understand inner loop range

   The inner loop runs from 0 to n - i - 1 because after each pass, the last i elements are sorted.

2. Step 2: Check each option

   for (int j = 0; j < n - i - 1; j++) correctly uses j < n - i - 1 to avoid out-of-bound and unnecessary comparisons.

3. Final Answer:

   for (int j = 0; j < n - i - 1; j++) -> Option A

4. Quick Check:

   Inner loop limit = n - i - 1 [OK]

Hint: Inner loop stops before sorted elements at end [OK]

Common Mistakes:

• Using j < n instead of j < n - i - 1
• Starting j from 1 instead of 0
• Using <= instead of < causing out-of-bound

3. What will be the output of the following C++ code snippet?

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

medium

A. 3 5 4 8

B. 5 3 4 8

C. 8 5 4 3

D. 3 4 5 8

Solution

1. Step 1: Trace first pass of Bubble Sort

   Compare pairs: (5,3) swap -> {3,5,8,4}, (5,8) no swap, (8,4) swap -> {3,5,4,8}

2. Step 2: Trace second pass and final array

   Next pass: (3,5) no swap, (5,4) swap -> {3,4,5,8}, last pass no swaps needed.

3. Final Answer:

   3 4 5 8 -> Option D

4. Quick Check:

   Sorted array = 3 4 5 8 [OK]

Hint: Bubble Sort pushes largest to end each pass [OK]

Common Mistakes:

• Not swapping correctly on first pass
• Confusing order of swaps
• Printing unsorted array

4. Identify the error in the following Bubble Sort code snippet and select the correct fix:

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

medium

A. Add a swap flag to optimize and stop early if sorted

B. Change outer loop to i < n - 1 to reduce unnecessary passes

C. Change inner loop to j < n - i - 1 to avoid out-of-bound access

D. No error, code is correct

Solution

1. Step 1: Analyze inner loop condition

   Inner loop uses j < n - i, but accesses arr[j + 1], which causes out-of-bound when j = n - i - 1.

2. Step 2: Correct inner loop limit

   Changing to j < n - i - 1 prevents accessing arr[n], fixing runtime error.

3. Final Answer:

   Change inner loop to j < n - i - 1 to avoid out-of-bound access -> Option C

4. Quick Check:

   Inner loop limit fixes out-of-bound [OK]

Hint: Inner loop must stop before last compared index [OK]

Common Mistakes:

• Ignoring out-of-bound access
• Changing outer loop only
• Assuming code is correct without checking array access

5. Given an array arr = {7, 2, 9, 4, 3}, how many total swaps will Bubble Sort perform to sort it in ascending order?

hard

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace swaps in each pass

   Pass 1: (7,2) swap, (7,9) no, (9,4) swap, (9,3) swap -> 3 swaps
   Array now: {2,7,4,3,9}

2. Step 2: Continue tracing swaps

   Pass 2: (2,7) no, (7,4) swap, (7,3) swap -> 2 swaps
   Array now: {2,4,3,7,9}
   Pass 3: (2,4) no, (4,3) swap -> 1 swap
   Array now: {2,3,4,7,9}
   Pass 4: no swaps

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Total swaps counted = 6 [OK]

Hint: Count swaps each pass until no swaps left [OK]

Common Mistakes:

• Counting comparisons instead of swaps
• Stopping early without counting all passes
• Miscounting swaps in passes