Bubble Sort Algorithm in DSA Python - Build from Scratch

Bubble Sort Algorithm

📖 Scenario: You are helping a librarian organize a small shelf of books by their ID numbers. The books are currently in a random order, and you want to arrange them from smallest to largest ID using a simple sorting method.

🎯 Goal: Build a program that sorts a list of book IDs using the bubble sort algorithm. You will create the list, set up a variable for the number of books, implement the bubble sort logic, and finally print the sorted list.

📋 What You'll Learn

Create a list called book_ids with these exact values: [23, 12, 45, 7, 19]

Create a variable called n that stores the length of book_ids

Use nested for loops with variables i and j to implement bubble sort on book_ids

Swap elements in book_ids when the current element is greater than the next element

Print the sorted book_ids list at the end

💡 Why This Matters

🌍 Real World

Sorting is used in libraries, stores, and apps to organize items so they are easy to find.

💼 Career

Understanding sorting algorithms like bubble sort helps in software development and data processing tasks.

1

Create the list of book IDs

Create a list called book_ids with these exact values: [23, 12, 45, 7, 19]

DSA Python

# Create the list book_ids with the given values
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Set the length variable

Create a variable called n that stores the length of the list book_ids using the len() function

DSA Python

book_ids = [23, 12, 45, 7, 19]
# Create variable n to store length of book_ids
# Your code here

Hint

Use len(book_ids) to get the number of items in the list.

3

Implement the bubble sort logic

Use nested for loops with variables i and j to implement bubble sort on book_ids. Swap elements when book_ids[j] is greater than book_ids[j + 1]

DSA Python

book_ids = [23, 12, 45, 7, 19]
n = len(book_ids)
# Implement bubble sort using for loops and swapping
# Your code here

Hint

Use two loops: the outer loop runs from 0 to n, the inner loop runs from 0 to n - i - 1. Swap elements if the current is greater than the next.

4

Print the sorted list

Print the sorted list book_ids using print(book_ids)

DSA Python

book_ids = [23, 12, 45, 7, 19]
n = len(book_ids)
for i in range(n):
    for j in range(0, n - i - 1):
        if book_ids[j] > book_ids[j + 1]:
            book_ids[j], book_ids[j + 1] = book_ids[j + 1], book_ids[j]
# Print the sorted book_ids list
# Your code here

Hint

Use print(book_ids) to show the sorted list.

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