Bubble Sort Algorithm in DSA C# - Execution Trace

Concept Flow - Bubble Sort Algorithm

Start with array

↓

Compare adjacent elements

↓

If left > right?

Yes No↓

Swap elements

↓

Continue until end of array

↓

If any swap happened?

Yes No↓

Repeat passes

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

Execution Sample

DSA C#

int[] arr = {5, 3, 8, 1, 2};

bool swapped;
for (int i = 0; i < arr.Length - 1; i++) {
  swapped = false;
  for (int j = 0; j < arr.Length - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
      int temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
      swapped = true;
    }
  }
  if (!swapped) {
    break;
  }
}

This code sorts the array 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	-	No	[1, 2, 3, 5, 8]

💡 No swaps in last pass means array is sorted

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	0	-

Key Moments - 3 Insights

Why does the inner loop run fewer times each pass?

Because after each pass, the largest unsorted element moves to its correct position at the end, so we don't need to check it again (see execution_table rows 1.4, 2.3, 3.2).

Why do we stop when no swaps happen in a pass?

No swaps mean the array is already sorted, so continuing would be unnecessary (see execution_table Exit row).

Why compare arr[j] and arr[j+1] and not other pairs?

Bubble Sort compares adjacent pairs to 'bubble' the largest element to the end step by step (see execution_table comparisons in each step).

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Array State' column in execution_table row 1.3

At which step does the algorithm detect the array is sorted and stops?

A After step 3.2

B After step 4.1

C After step 2.3

D After step 1.4

💡 Hint

Look at the 'Exit' row in execution_table where no swaps happen

If the array started as [1, 2, 3, 5, 8], how would the execution_table change?

A No swaps would occur, algorithm stops after first pass

B Many swaps would occur as usual

C Algorithm would run infinitely

D Array would be reversed

💡 Hint

Refer to the exit condition in execution_table where no swaps means sorted

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left element is greater
- Largest elements 'bubble' to the end each pass
- Stop when a pass has no swaps
- Time complexity: O(n²) in worst case

Full Transcript

Bubble Sort works by comparing each pair of adjacent elements in the array. If the left element is bigger, they swap places. This process repeats for the entire array, pushing the largest unsorted element to the end. Each pass reduces the number of elements to check because the end elements are sorted. The algorithm stops when a full pass completes with no swaps, meaning the array is sorted. The execution table shows each comparison and swap step, and the variable tracker shows how the array and loop counters change over time.

Practice

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

easy

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

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

C. Use a pivot to partition the list into smaller parts

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

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 continues until the list is sorted, which matches Repeatedly swap adjacent elements if they are in the wrong order.

3. Final Answer:

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

4. Quick Check:

   Bubble Sort = Swap neighbors [OK]

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

Common Mistakes:

• Confusing Bubble Sort with Quick Sort or Merge Sort
• Thinking it divides the list into parts
• Assuming it inserts elements like Insertion Sort

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[i+1] in C# during Bubble Sort?

easy

A. temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;

B. arr[i] = arr[i+1]; arr[i+1] = arr[i];

C. arr[i], arr[i+1] = arr[i+1], arr[i];

D. swap(arr[i], arr[i+1]);

Solution

1. Step 1: Understand swapping in C#

   C# does not support tuple unpacking or direct swap functions by default, so a temporary variable is needed.

2. Step 2: Identify correct swap syntax

   Using a temporary variable to hold one value, then swapping is correct as in temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; -> Option A

4. Quick Check:

   Use temp variable to swap [OK]

Hint: Use a temp variable to swap two elements in C# [OK]

Common Mistakes:

• Trying to swap without a temp variable
• Using Python-style tuple swap syntax
• Assuming a built-in swap function exists

3. What will be the output of the following C# code snippet after applying one full pass of Bubble Sort?

int[] arr = {5, 3, 8, 4};
for (int i = 0; i < arr.Length - 1; i++) {
  if (arr[i] > arr[i + 1]) {
    int temp = arr[i];
    arr[i] = arr[i + 1];
    arr[i + 1] = temp;
  }
}
Console.WriteLine(string.Join(", ", arr));

medium

A. 3, 5, 4, 8

B. 3, 4, 5, 8

C. 5, 3, 4, 8

D. 8, 5, 4, 3

Solution

1. Step 1: Perform one pass of Bubble Sort on array

   Start with arr = [5, 3, 8, 4]. Compare pairs:
   5 > 3? Yes, swap -> [3, 5, 8, 4]
   5 > 8? No swap
   8 > 4? Yes, swap -> [3, 5, 4, 8]

2. Step 2: Final array after one pass

   After one pass, array is [3, 5, 4, 8].

3. Final Answer:

   3, 5, 4, 8 -> Option A

4. Quick Check:

   One pass swaps neighbors to bubble largest to end [OK]

Hint: One pass moves largest element to the end [OK]

Common Mistakes:

• Assuming full sort after one pass
• Not swapping last pair correctly
• Confusing indices in loop

4. Identify the error in this Bubble Sort code snippet and choose the correct fix:

int[] arr = {4, 2, 7, 1};
for (int i = 0; i < arr.Length; i++) {
  for (int j = 0; j < arr.Length; 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 i < arr.Length - 1

B. Change inner loop condition to j < arr.Length - 1

C. Remove the inner loop completely

D. Swap arr[i] and arr[j] instead of arr[j] and arr[j+1]

Solution

1. Step 1: Analyze inner loop range

   The inner loop uses j from 0 to arr.Length, but accesses arr[j+1]. This causes out-of-range error when j = arr.Length - 1.

2. Step 2: Fix inner loop condition

   Changing inner loop to j < arr.Length - 1 prevents accessing arr[arr.Length], fixing the error.

3. Final Answer:

   Change inner loop condition to j < arr.Length - 1 -> Option B

4. Quick Check:

   Prevent out-of-range by limiting inner loop [OK]

Hint: Inner loop must stop before last index to avoid errors [OK]

Common Mistakes:

• Not adjusting inner loop range
• Changing outer loop incorrectly
• Misunderstanding which indices to swap

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

hard

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Trace swaps during Bubble Sort passes

   Initial array: [7, 2, 9, 4, 3]
   Pass 1:
   7 > 2? Swap -> [2, 7, 9, 4, 3] (1 swap)
   7 > 9? No swap
   9 > 4? Swap -> [2, 7, 4, 9, 3] (2 swaps)
   9 > 3? Swap -> [2, 7, 4, 3, 9] (3 swaps)
   Pass 2:
   2 > 7? No swap
   7 > 4? Swap -> [2, 4, 7, 3, 9] (4 swaps)
   7 > 3? Swap -> [2, 4, 3, 7, 9] (5 swaps)
   Pass 3:
   2 > 4? No swap
   4 > 3? Swap -> [2, 3, 4, 7, 9] (6 swaps)
   Pass 4:
   No swaps needed, array sorted.

2. Step 2: Count total swaps

   Total swaps = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Count swaps each pass carefully [OK]

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

Common Mistakes:

• Counting only first pass swaps
• Forgetting swaps in later passes
• Assuming swaps equal number of elements