Bubble Sort Algorithm in DSA C

Mental Model

Bubble sort repeatedly swaps adjacent items if they are in the wrong order, like bubbles rising to the surface.

Analogy: Imagine a row of kids holding numbered cards. Each round, pairs of neighbors compare cards and swap if the left card is bigger, so the biggest card 'bubbles' to the right end.

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: Smaller number moves left, bigger moves right

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

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

Why: Order is correct, no change

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

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

Why: Bigger number moves right

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

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

Why: Biggest number bubbles to the end

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

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

Why: First two are in 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: 5 moves right, 2 moves left

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

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

Why: Order is correct

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

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

Why: Smaller number moves left

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

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

Why: Smallest number moves left

Step 11: No swaps in next pass, sorting done

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

Why: Array is sorted

Result:

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

Annotated Code

DSA C

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = 0; // Track if any swap happens in this pass
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1; // Mark swap happened
            }
        }
        if (swapped == 0) {
            // No swaps means array is sorted
            break;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" -> ");
    }
    printf("\n");
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);
    printArray(arr, n);

    return 0;
}

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

outer loop controls passes over the array

swapped = 0; // Track if any swap happens in this pass

reset swap flag at start of each pass

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

inner loop compares adjacent pairs up to last sorted element

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

compare adjacent elements to decide if swap needed

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

swap elements to move bigger one right

swapped = 1; // Mark swap happened

record that a swap occurred this pass

if (swapped == 0) { break; }

stop early if no swaps, array is sorted

Output

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

Complexity Analysis

Time: O(n^2) because in worst case we compare and swap pairs in nested loops over n elements

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

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

Edge Cases

empty array

function returns immediately without errors

DSA C

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

array with one element

no swaps needed, array remains same

DSA C

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

already sorted array

early break after first pass because swapped remains 0

DSA C

if (swapped == 0) { break; }

When to Use This Pattern

When you see a problem asking to sort by repeatedly swapping neighbors until order is correct, reach for bubble sort because it simulates 'bubbling' the largest values to the end step by step.

Common Mistakes

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

Mistake: Not using a swapped flag to stop early, causing extra passes
Fix: Add a swapped flag and break outer loop if no swaps happen in a pass

Summary

Bubble sort repeatedly swaps adjacent elements to sort an array.

Use it to understand basic sorting or when simplicity is more important than speed.

The key insight is that the largest unsorted element 'bubbles' to its correct position each pass.

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