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 comparisons

Yes↓

Array sorted -> End

Bubble Sort repeatedly compares and swaps adjacent elements if they are in the wrong order, passing through the array until sorted.

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]) {
      int temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}

This code sorts the array using Bubble Sort by repeatedly swapping adjacent elements if they are out of order.

Execution Table

Step	Operation	Comparison	Swap?	Array State
1.1	Compare arr[0] and arr[1]	5 > 3	Yes	[3, 5, 8, 1, 2]
1.2	Compare arr[1] and arr[2]	5 > 8	No	[3, 5, 8, 1, 2]
1.3	Compare arr[2] and arr[3]	8 > 1	Yes	[3, 5, 1, 8, 2]
1.4	Compare arr[3] and arr[4]	8 > 2	Yes	[3, 5, 1, 2, 8]
2.1	Compare arr[0] and arr[1]	3 > 5	No	[3, 5, 1, 2, 8]
2.2	Compare arr[1] and arr[2]	5 > 1	Yes	[3, 1, 5, 2, 8]
2.3	Compare arr[2] and arr[3]	5 > 2	Yes	[3, 1, 2, 5, 8]
3.1	Compare arr[0] and arr[1]	3 > 1	Yes	[1, 3, 2, 5, 8]
3.2	Compare arr[1] and arr[2]	3 > 2	Yes	[1, 2, 3, 5, 8]
4.1	Compare arr[0] and arr[1]	1 > 2	No	[1, 2, 3, 5, 8]
Exit	No swaps in last pass or all passes done	-	-	[1, 2, 3, 5, 8]

💡 All elements are sorted after 4 passes; no swaps needed in last pass.

Variable Tracker

Variable	Start	After 1.1	After 1.4	After 2.3	After 3.2	After 4.1	Final
arr	[5, 3, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 1, 2, 8]	[3, 1, 2, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]
i	0	0	0	1	2	3	4
j	0	1	3	2	2	1	-

Key Moments - 3 Insights

Why do we reduce the inner loop's range by 'i' each pass?

Because after each pass, the largest element settles at the end, so we don't need to compare it again. See execution_table rows 1.4, 2.3, 3.2 where the last elements are already sorted.

Why does the algorithm stop after no swaps in a pass?

No swaps mean the array is sorted. The exit row shows the final pass with no swaps, confirming sorting is complete.

Why do we compare arr[j] and arr[j+1] instead of other pairs?

Bubble Sort compares adjacent pairs to 'bubble' the largest element to the right. This is shown in each step comparing arr[j] and arr[j+1] in the execution_table.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Array State' column for step 1.3 in the execution_table.

At which step does the array first become fully sorted?

A After step 4.1

B After step 3.2

C After step 2.3

D After step 1.4

💡 Hint

Look at the array states after each step in the execution_table; the sorted array is [1, 2, 3, 5, 8].

If we remove the swap condition, what happens to the array state in the execution_table?

A Array remains unchanged throughout

B Array becomes sorted faster

C Array gets reversed

D Array partially sorts

💡 Hint

Without swaps, the array elements never change positions; check the 'Swap?' column for guidance.

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left element is greater
- Largest elements 'bubble' to the end each pass
- Reduce inner loop range by pass count
- Stop when no swaps occur in a pass
- Simple but inefficient for large arrays

Full Transcript

Bubble Sort works by comparing pairs of adjacent elements in an array. If the left element is bigger, they swap places. This process repeats, pushing the largest unsorted element to the end each pass. The inner loop shortens each time because the last elements become sorted. The algorithm stops when a full pass has no swaps, meaning the array is sorted. This trace shows each comparison, swap decision, and array state after each step, helping visualize how the array gradually becomes sorted.

Practice

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

easy

A. Use a pivot to partition the array into smaller parts

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

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

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

Solution

1. Step 1: Understand the sorting method

   Bubble sort works by comparing adjacent elements and swapping them if they are out of order.

2. Step 2: Identify the correct description

   Repeatedly swap adjacent elements if they are in the wrong order describes this swapping of neighbors repeatedly until sorted.

3. Final Answer:

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

4. Quick Check:

   Bubble sort = swapping neighbors [OK]

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

Common Mistakes:

• Confusing bubble sort with divide and conquer methods
• Thinking bubble sort uses a pivot element
• Mixing bubble sort with insertion sort logic

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; j++)

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

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

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

Solution

1. Step 1: Understand the 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: Match the correct loop syntax

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Inner loop stops before last sorted elements [OK]

Common Mistakes:

• Using j < n causes out-of-bound access
• Starting j from 1 misses first element comparison
• Using <= instead of < causes extra iteration

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

int arr[] = {4, 2, 3};
int n = 3;
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++) {
  printf("%d ", arr[i]);
}

medium

A. 2 4 3

B. 4 3 2

C. 3 2 4

D. 2 3 4

Solution

1. Step 1: Trace first pass of bubble sort

   Compare 4 and 2, swap -> arr = {2, 4, 3}; then compare 4 and 3, swap -> arr = {2, 3, 4}

2. Step 2: Trace second pass and final array

   Second pass compares 2 and 3 (no swap), 3 and 4 (no swap). Array remains {2, 3, 4}.

3. Final Answer:

   2 3 4 -> Option D

4. Quick Check:

   Sorted array = 2 3 4 [OK]

Hint: Bubble sort sorts array ascending by swapping neighbors [OK]

Common Mistakes:

• Not swapping correctly on first pass
• Printing unsorted array
• Confusing loop limits causing partial sort

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 - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

medium

A. Change outer loop to for (int i = 0; i < n - 1; i++)

B. Change inner loop to for (int j = 1; j < n; j++)

C. Remove the swap inside the if condition

D. Change outer loop to for (int i = 1; i < n; i++)

Solution

1. Step 1: Analyze loop ranges for bubble sort

   The outer loop should be for (int i = 0; i < n - 1; i++) because after n-1 passes, array is sorted, avoiding an unnecessary pass.

2. Step 2: Identify the fix

   Change outer loop to for (int i = 0; i < n - 1; i++) correctly optimizes by limiting to n-1 passes.

3. Final Answer:

   Change outer loop to for (int i = 0; i < n - 1; i++) -> Option A

4. Quick Check:

   Outer loop limit = n - 1 [OK]

Hint: Outer loop runs n-1 times in bubble sort [OK]

Common Mistakes:

• Running outer loop n times wastes time
• Changing inner loop start incorrectly
• Removing swap breaks sorting logic

5. Given an array arr = {5, 1, 4, 2, 8}, how many total swaps will bubble sort perform to sort it in ascending order?

hard

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Trace pass 1 (i=0, j < 4)

   Initial: {5,1,4,2,8}
   j=0: 5>1 swap -> {1,5,4,2,8} (1)
   j=1: 5>4 swap -> {1,4,5,2,8} (2)
   j=2: 5>2 swap -> {1,4,2,5,8} (3)
   j=3: 5<8 no -> 3 swaps, array: {1,4,2,5,8}

2. Step 2: Trace pass 2 (i=1, j < 3)

   j=0: 1<4 no
   j=1: 4>2 swap -> {1,2,4,5,8} (4)
   j=2: 4<5 no -> 1 swap, total 4, array: {1,2,4,5,8}

3. Step 3: Trace pass 3 (i=2, j < 2)

   j=0: 1<2 no
   j=1: 2<4 no -> 0 swaps, total 4

4. Step 4: Trace pass 4 (i=3, j < 1)

   j=0: 1<2 no -> 0 swaps, total 4

5. Step 5: Total swaps counted = 4

   But we missed one swap in pass 2: Actually, pass 2 has 1 swap (4>2), pass 3 has 0 swaps, pass 4 has 0 swaps. Total swaps = 4.

6. Recounting carefully:

   Pass 1: 3 swaps
   Pass 2: 1 swap
   Pass 3: 0 swaps
   Pass 4: 0 swaps
   Total = 4 swaps

7. Final Answer:

   4 -> Option A

8. Quick Check:

   Total swaps counted = 4 [OK]

Hint: Count swaps each pass carefully to avoid overcounting [OK]

Common Mistakes:

• Counting non-swaps as swaps
• Assuming max swaps per pass without checking
• Forgetting that last elements get sorted early