Bubble Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Bubble Sort Algorithm

Start with unsorted array

↓

Compare adjacent elements

↓

If left > right?

Yes→Swap elements

↓

Move to next pair

↓

Reach end of array?

No→Repeat compare-swap

Yes↓

Array sorted?

No→Repeat entire process

Yes↓

Done

Bubble Sort repeatedly compares and swaps adjacent elements if they are in the wrong order, passing through the array multiple times until sorted.

Execution Sample

DSA Python

arr = [5, 3, 8, 1, 2]
for i in range(len(arr)):
    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)

This code sorts the array by repeatedly swapping adjacent elements if they are out of order.

Execution Table

Step	Operation	Comparison	Swap?	Array State
1.1	Compare arr[0] and arr[1]	5 > 3	Yes	[3, 5, 8, 1, 2]
1.2	Compare arr[1] and arr[2]	5 > 8	No	[3, 5, 8, 1, 2]
1.3	Compare arr[2] and arr[3]	8 > 1	Yes	[3, 5, 1, 8, 2]
1.4	Compare arr[3] and arr[4]	8 > 2	Yes	[3, 5, 1, 2, 8]
2.1	Compare arr[0] and arr[1]	3 > 5	No	[3, 5, 1, 2, 8]
2.2	Compare arr[1] and arr[2]	5 > 1	Yes	[3, 1, 5, 2, 8]
2.3	Compare arr[2] and arr[3]	5 > 2	Yes	[3, 1, 2, 5, 8]
3.1	Compare arr[0] and arr[1]	3 > 1	Yes	[1, 3, 2, 5, 8]
3.2	Compare arr[1] and arr[2]	3 > 2	Yes	[1, 2, 3, 5, 8]
4.1	Compare arr[0] and arr[1]	1 > 2	No	[1, 2, 3, 5, 8]
Exit	No swaps in last pass	Array sorted	No	[1, 2, 3, 5, 8]

💡 No swaps in the last pass, array is sorted

Variable Tracker

Variable	Start	After 1.1	After 1.3	After 1.4	After 2.3	After 3.2	Final
arr	[5, 3, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 1, 8, 2]	[3, 5, 1, 2, 8]	[3, 1, 2, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]
i	0	0	0	0	1	2	4
j	0	1	3	4	3	2	-

Key Moments - 3 Insights

Why do we stop inner loop earlier each pass (len(arr)-1-i)?

Because after each pass, the largest element settles at the end, so we don't need to compare it again. See execution_table rows 1.4, 2.3, 3.2 where the last elements are already sorted.

Why do we compare arr[j] and arr[j+1] and not arr[j-1]?

We compare adjacent pairs moving forward to bubble the largest element to the right. Comparing backward would not follow the bubble sort logic. This is shown in execution_table where j moves from 0 upwards.

What happens if no swaps occur in a pass?

If no swaps happen, the array is sorted and we can stop early. This is shown in the last row of execution_table where no swaps occur and sorting ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 1.3, what is the array state after the swap?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 1.3 in execution_table

At which step does the array become fully sorted?

A After step 3.2

B After step 2.3

C After step 4.1

D After step 1.4

💡 Hint

Look at the 'Array State' column and see when the array is in ascending order

If we remove '-i' from inner loop range, what happens?

A The algorithm runs faster

B The algorithm may do unnecessary comparisons

C The array will not be sorted

D The array will be sorted in descending order

💡 Hint

Refer to key_moments about why inner loop shortens each pass

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left element is greater
- Largest elements 'bubble' to the end each pass
- Inner loop shortens each pass by 1
- Stop early if no swaps in a pass
- Time complexity: O(n²) average and worst

Full Transcript

Bubble Sort works by comparing pairs of adjacent elements in an array. If the left element is bigger, they swap places. This process repeats, pushing the largest unsorted element to the end each pass. Each pass requires fewer comparisons because the end elements become sorted. If a pass completes with no swaps, the array is sorted and the algorithm stops early. The code uses two loops: the outer loop for passes, and the inner loop for comparisons and swaps. This visual trace shows each comparison, swap, and the array state after each step, helping beginners see how the array gradually becomes sorted.

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