Bird
Raised Fist0
DSA Pythonprogramming~5 mins

Bubble Sort Algorithm in DSA Python - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Bubble Sort Algorithm
O(nĀ²)
Understanding Time Complexity

We want to understand how the time taken by Bubble Sort changes as the list size grows.

How does the number of steps increase when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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]

This code sorts a list by repeatedly swapping adjacent elements if they are in the wrong order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: Comparing and possibly swapping adjacent elements inside nested loops.
  • How many times: Outer loop runs n times; inner loop runs decreasing times from n-1 down to 1, totaling about n*(n-1)/2 comparisons.
How Execution Grows With Input

As the list size grows, the number of comparisons grows roughly with the square of the size.

Input Size (n)Approx. Operations
10About 45 comparisons
100About 4,950 comparisons
1000About 499,500 comparisons

Pattern observation: Doubling the list size roughly quadruples the number of operations.

Final Time Complexity

Time Complexity: O(nĀ²)

This means the time to sort grows roughly with the square of the list size, so bigger lists take much longer.

Common Mistake

[X] Wrong: "Bubble Sort always takes the same time no matter the list order."

[OK] Correct: If the list is already sorted, Bubble Sort can finish faster because it does fewer swaps, but the loops still run, so time varies with input order.

Interview Connect

Understanding Bubble Sort's time complexity helps you compare it with faster sorting methods and shows your grasp of algorithm efficiency.

Self-Check

"What if we add a flag to stop early when no swaps happen? How would the time complexity change in the best case?"

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard