Bubble Sort Algorithm in DSA C#

Mental Model

Bubble sort repeatedly swaps adjacent items if they are in the wrong order, pushing the largest unsorted item to the end each pass.

Analogy: Imagine bubbles rising in water: the biggest bubble slowly moves up to the surface by swapping places with smaller bubbles below it.

Index: 0   1   2   3   4
Array: [5]->[3]->[8]->[4]->[2]

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Sort the array in ascending order using bubble sort

Step 1: Compare 5 and 3, swap because 5 > 3

[3] -> [5] -> [8] -> [4] -> [2]

Why: We want smaller numbers to move left, so swap adjacent if left is bigger

Step 2: Compare 5 and 8, no swap because 5 < 8

[3] -> [5] -> [8] -> [4] -> [2]

Why: No swap needed if left number is smaller

Step 3: Compare 8 and 4, swap because 8 > 4

[3] -> [5] -> [4] -> [8] -> [2]

Why: Push bigger number 8 towards the right

Step 4: Compare 8 and 2, swap because 8 > 2

[3] -> [5] -> [4] -> [2] -> [8]

Why: Largest number 8 bubbles to the end

Step 5: Start second pass: compare 3 and 5, no swap

[3] -> [5] -> [4] -> [2] -> [8]

Why: Check next pair for order

Step 6: Compare 5 and 4, swap because 5 > 4

[3] -> [4] -> [5] -> [2] -> [8]

Why: Smaller number moves left

Step 7: Compare 5 and 2, swap because 5 > 2

[3] -> [4] -> [2] -> [5] -> [8]

Why: Push 5 closer to its correct position

Step 8: Start third pass: compare 3 and 4, no swap

[3] -> [4] -> [2] -> [5] -> [8]

Why: Check order of next pair

Step 9: Compare 4 and 2, swap because 4 > 2

[3] -> [2] -> [4] -> [5] -> [8]

Why: Move smaller number left

Step 10: Start fourth pass: compare 3 and 2, swap because 3 > 2

[2] -> [3] -> [4] -> [5] -> [8]

Why: Final swap to sort array

Result:

[2] -> [3] -> [4] -> [5] -> [8]

Annotated Code

DSA C#

using System;

class BubbleSort {
    public static void Sort(int[] arr) {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++) {
            // Each pass pushes largest unsorted element to the end
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap if left element is bigger
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void PrintArray(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i < arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }

    static void Main() {
        int[] arr = {5, 3, 8, 4, 2};
        Console.WriteLine("Original array:");
        PrintArray(arr);
        Sort(arr);
        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }
}

for (int i = 0; i < n - 1; i++) {

repeat passes to bubble largest unsorted element to the end

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

compare adjacent pairs up to last unsorted element

if (arr[j] > arr[j + 1]) {

check if left element is bigger to decide swap

int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;

swap adjacent elements to move bigger one right

Output

Original array:

5 -> 3 -> 8 -> 4 -> 2 -> null

Sorted array:

2 -> 3 -> 4 -> 5 -> 8 -> null

Complexity Analysis

Time: O(n^2) because each element is compared with others in nested loops

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to more advanced sorts like quicksort (O(n log n)), bubble sort is slower but simpler to understand

Edge Cases

empty array

no operations, array remains empty

DSA C#

for (int i = 0; i < n - 1; i++) {

array with one element

no swaps needed, array stays the same

DSA C#

for (int i = 0; i < n - 1; i++) {

array already sorted

no swaps occur, but algorithm still runs all passes

DSA C#

if (arr[j] > arr[j + 1]) {

When to Use This Pattern

When you see a problem asking to sort a small list with simple swaps, bubble sort is a good first approach because it repeatedly swaps adjacent elements to order the list.

Common Mistakes

Mistake: Not reducing the inner loop range each pass, causing unnecessary comparisons
Fix: Use 'n - i - 1' as the inner loop limit to avoid checking already sorted elements

Mistake: Swapping elements incorrectly or forgetting to swap
Fix: Ensure swap code exchanges both elements properly using a temporary variable

Summary

Bubble sort repeatedly swaps adjacent elements to sort the array.

Use it for small or nearly sorted lists where simplicity matters more than speed.

The key insight is that the largest unsorted element 'bubbles' to the end each pass.

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