Bubble Sort Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bubble Sort on a small list

What is the output of the following bubble sort code after sorting the list?

DSA Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

lst = [4, 2, 5, 1]
bubble_sort(lst)
print(lst)

A [1, 2, 4, 5]

B [1, 2, 5, 4]

C [4, 2, 1, 5]

D [5, 4, 2, 1]

💡 Hint

Remember bubble sort swaps adjacent elements if they are in the wrong order.

Bubble sort compares pairs and swaps them to move the largest elements to the end step by step. After sorting, the list is in ascending order.

🧠 Conceptual

intermediate

Number of passes in Bubble Sort

For a list of length n, how many passes (outer loop iterations) does the bubble sort algorithm perform in the worst case?

A n

B n/2

C n+1

D n-1

💡 Hint

Think about how many times the largest element needs to bubble up to the end.

Bubble sort performs n-1 passes because after n-1 passes, the list is guaranteed to be sorted.

🔧 Debug

advanced

Identify the error in this bubble sort code

What error will this bubble sort code produce when run?

DSA Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

lst = [3, 1, 2]
bubble_sort(lst)
print(lst)

A [1, 2, 3]

B TypeError: unsupported operand type(s)

C IndexError: list index out of range

D No error, prints [3, 1, 2]

💡 Hint

Check the inner loop range and the index used for accessing arr[j+1].

The inner loop runs up to n-i, so arr[j+1] accesses an index outside the list on the last iteration causing IndexError.

❓ Predict Output

advanced

Output after partial bubble sort passes

What is the state of the list after the first pass (outer loop iteration) of bubble sort on this list?

DSA Python

lst = [5, 3, 4, 1, 2]

n = len(lst)
for j in range(n-1):
    if lst[j] > lst[j+1]:
        lst[j], lst[j+1] = lst[j+1], lst[j]

print(lst)

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

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

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

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

💡 Hint

The largest element moves to the end after the first pass.

After one pass, the largest number 5 bubbles to the last position, other elements are partially sorted.

🚀 Application

expert

Minimum swaps in bubble sort for a nearly sorted list

Given the list [1, 2, 4, 3, 5], how many swaps will bubble sort perform to sort it completely?

DSA Python

def bubble_sort_count_swaps(arr):
    n = len(arr)
    swaps = 0
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swaps += 1
    return swaps

lst = [1, 2, 4, 3, 5]
print(bubble_sort_count_swaps(lst))

A 2

B 1

C 3

D 4

💡 Hint

4 and 3 are adjacent, so only one swap is needed.

Only one swap is needed: swap 4 and 3 once, then the list is sorted with no more swaps.

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. Repeatedly swap adjacent elements if they are in the wrong order

C. Select the smallest element and place it at the beginning

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

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: Compare with other sorting methods

   Other options describe different algorithms: divide and conquer, selection, and quicksort.

3. Final Answer:

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

4. Quick Check:

   Bubble Sort = Swap adjacent pairs [OK]

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

Common Mistakes:

• Confusing Bubble Sort with Selection Sort
• Thinking it divides the list like Merge Sort
• Mixing it up with Quick Sort pivot method

2. Which of the following is the correct syntax to start a bubble sort outer loop in Python for a list arr of length n?

easy

A. for i in range(n):

B. for i in range(1, n):

C. for i in range(n-1):

D. for i in range(n+1):

Solution

1. Step 1: Understand loop range for bubble sort

   The outer loop runs from 0 to n-2 because we compare pairs up to the second last element.

2. Step 2: Check each option's range

   for i in range(n-1): uses range(n-1), which means 0 to n-2, correct for bubble sort outer loop.

3. Final Answer:

   for i in range(n-1): -> Option C

4. Quick Check:

   Outer loop runs n-1 times [OK]

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

Common Mistakes:

• Using range(n) causes extra unnecessary iteration
• Starting loop at 1 misses first element
• Using range(n+1) causes index errors

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

arr = [4, 2, 3]
for i in range(len(arr)-1):
    for j in range(len(arr)-1-i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)

medium

A. [2, 3, 4]

B. [4, 3, 2]

C. [3, 2, 4]

D. [2, 4, 3]

Solution

1. Step 1: Trace first outer loop iteration (i=0)

   Inner loop runs j=0 to 1. Swaps 4 and 2 -> [2,4,3], then swaps 4 and 3 -> [2,3,4].

2. Step 2: Trace second outer loop iteration (i=1)

   Inner loop runs j=0 only. Compares 2 and 3, no swap needed. Array stays [2,3,4].

3. Final Answer:

   [2, 3, 4] -> Option A

4. Quick Check:

   Bubble Sort sorts ascending -> [2,3,4] [OK]

Hint: Bubble Sort outputs sorted list ascending [OK]

Common Mistakes:

• Not swapping correctly in inner loop
• Confusing loop ranges causing partial sort
• Printing before sorting completes

4. Identify the error in this bubble sort code snippet:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

medium

A. Inner loop should run till n-1-i, not n-1

B. Outer loop should run till n-1, not n

C. Swap syntax is incorrect

D. Function does not return anything

Solution

1. Step 1: Analyze inner loop range

   Inner loop runs from 0 to n-2 always, not reducing with i, causing unnecessary comparisons.

2. Step 2: Correct inner loop range

   It should be range(n-1-i) to avoid checking already sorted elements at the end.

3. Final Answer:

   Inner loop should run till n-1-i, not n-1 -> Option A

4. Quick Check:

   Inner loop shrinks each pass [OK]

Hint: Inner loop shrinks by i each outer iteration [OK]

Common Mistakes:

• Not reducing inner loop range wastes time
• Incorrect swap syntax causes errors
• Forgetting to return sorted array

5. Given the list arr = [5, 1, 4, 2, 8], how many total swaps will bubble sort perform to sort it in ascending order?

hard

A. 4

B. 7

C. 6

D. 5

Solution

1. Step 1: Trace Pass 1 (i=0)

   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 swap.

2. Step 2: Trace Pass 2 (i=1)

   j=0: 1<4 no
   j=1: 4>2 swap [1,2,4,5,8] (4)
   j=2: 4<5 no.

3. Step 3: Trace Pass 3 (i=2)

   j=0: 1<2 no
   j=1: 2>4 no swap (no swap)
   No swaps in this pass.

4. Step 4: Trace Pass 4 (i=3)

   j=0: 1<2 no swap
   No swaps in this pass.

5. Step 5: Total swaps

   Total swaps so far: 4 (Pass 1) + 1 (Pass 2) = 5 swaps. But we missed one swap in Pass 2 or 3? Let's re-check.

6. Re-check Pass 2

   j=1: 4>2 swap (4th swap)
   j=2: 4<5 no swap

7. Pass 3

   j=0: 1<2 no swap
   j=1: 2<4 no swap

8. Pass 4

   j=0: 1<2 no swap

9. Step 6: Final count

   Total swaps = 4 (Pass 1) + 1 (Pass 2) = 5 swaps.

10. Final Answer:

    5 -> Option D

11. Quick Check:

    Count swaps carefully by tracing each pass [OK]

Hint: Count swaps by tracing each adjacent pair swap [OK]

Common Mistakes:

• Counting comparisons instead of swaps
• Missing swaps in later passes
• Assuming swaps equal number of elements