Bubble Sort Algorithm in DSA Python

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: list: [5, 3, 8, 4, 2]

Goal: Sort the list 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 if left is bigger

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

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

Why: Order is correct here, no swap needed

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

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

Why: 8 is bigger, so it moves right

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

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

Why: 8 moves to the end, largest element bubbled up

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

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

Why: 3 < 5, order is correct

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

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

Why: 5 moves right to correct position

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

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

Why: 5 moves right again

Step 8: Third pass: compare 3 and 4, no swap

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

Why: 3 < 4, order is correct

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

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

Why: 4 moves right

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

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

Why: 2 moves left to correct position

Step 11: No swaps in next pass, sorting done

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

Why: List is sorted, no swaps means done

Result:

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

Annotated Code

DSA Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # swap
                swapped = True
        if not swapped:
            break

# Driver code
arr = [5, 3, 8, 4, 2]
bubble_sort(arr)
print(' -> '.join(str(x) for x in arr))

for i in range(n):

repeat passes over the array to bubble up largest unsorted element

swapped = False

track if any swap happens this pass to optimize early stop

for j in range(0, n - i - 1):

compare adjacent pairs up to last unsorted element

if arr[j] > arr[j + 1]:

check if current pair is out of order

arr[j], arr[j + 1] = arr[j + 1], arr[j] # swap

swap to move bigger element right

swapped = True

mark that a swap happened this pass

if not swapped:

if no swaps, array is sorted, stop early

break

exit the sorting loop early

Output

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

Complexity Analysis

Time: O(n^2) because in worst case we compare each pair multiple times 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 and implement

Edge Cases

empty list

function returns immediately without error

DSA Python

for i in range(n):

list with one element

no swaps needed, returns immediately

DSA Python

for i in range(n):

already sorted list

early stop after first pass due to no swaps

DSA Python

if not swapped:

When to Use This Pattern

When you see a problem asking to sort a small list or teach sorting basics, bubble sort is a good starting pattern because it uses simple adjacent swaps to order elements.

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: Forgetting to swap elements when out of order
Fix: Add the swap operation inside the if condition comparing adjacent elements

Mistake: Not using a swapped flag to stop early, causing extra passes
Fix: Use a boolean flag to detect if any swap happened and break early if none

Summary

Bubble sort repeatedly swaps adjacent elements to sort a list in ascending order.

Use bubble sort to understand basic sorting and when working with small or nearly sorted lists.

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