Bubble Sort Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Bubble Sort algorithm?

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, "bubbling" the largest unsorted element to its correct position in each pass.

beginner

How many passes does Bubble Sort make in the worst case for an array of size n?

In the worst case, Bubble Sort makes n-1 passes through the array to fully sort it.

intermediate

What is the time complexity of Bubble Sort in the average and worst cases?

The time complexity is O(n²) because it compares pairs of elements multiple times in nested loops.

intermediate

What optimization can be added to Bubble Sort to stop early if the array is already sorted?

Add a flag to check if any swaps happened in a pass. If no swaps occur, the array is sorted and the algorithm can stop early.

beginner

Show the state of the array [5, 3, 8, 4, 2] after the first pass of Bubble Sort.

After first pass: [3, 5, 4, 2, 8] because 5 and 3 swapped, 8 and 4 swapped, and 8 and 2 swapped, moving the largest element 8 to the end.

What does Bubble Sort compare during its sorting process?

A Adjacent elements

B First and last elements

C Random elements

D Only the smallest elements

Bubble Sort compares adjacent elements to decide if they need to be swapped.

What is the best case time complexity of Bubble Sort when the array is already sorted?

A O(n²)

B O(n log n)

C O(n)

D O(log n)

With an optimization to stop early, Bubble Sort runs in O(n) time if the array is already sorted.

Which of these is true about Bubble Sort?

A It is a stable sorting algorithm

B It always sorts in O(n log n) time

C It uses extra memory proportional to n

D It sorts by dividing the array into halves

Bubble Sort is stable because it does not change the relative order of equal elements.

How does Bubble Sort move the largest element to its correct position?

A By swapping it with the smallest element

B By repeatedly swapping adjacent elements if they are in wrong order

C By inserting it at the beginning

D By dividing the array

Bubble Sort swaps adjacent elements to push the largest element to the end in each pass.

What happens if no swaps occur during a pass in Bubble Sort?

A The algorithm continues to next pass

B The array is reversed

C The algorithm restarts

D The array is considered sorted and algorithm stops

No swaps mean the array is sorted, so the algorithm can stop early.

Explain how Bubble Sort works step-by-step on a small array.

Think of bubbles rising to the surface in water.

Describe the time complexity of Bubble Sort and how it changes with optimization.

Consider how many comparisons and swaps happen in 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