Sorting algorithms (bubble, selection) in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ trace

intermediate

Trace the Bubble Sort Process

Given the list [5, 3, 8, 4], what is the list after the first full pass of bubble sort?

Intro to Computing

lst = [5, 3, 8, 4]
for i in range(len(lst)-1):
    if lst[i] > lst[i+1]:
        lst[i], lst[i+1] = lst[i+1], lst[i]

A [3, 5, 4, 8]

B [3, 4, 5, 8]

C [5, 3, 4, 8]

D [3, 5, 8, 4]

💡 Hint

Bubble sort compares adjacent pairs and swaps if the left is bigger.

After the first pass, the largest number moves to the end. The swaps are: 5 and 3 swap → [3,5,8,4], then 5 and 8 no swap, then 8 and 4 swap → [3,5,4,8].

🧠 Conceptual

intermediate

Selection Sort Key Idea

Which statement best describes the main idea of selection sort?

A Repeatedly find the smallest unsorted element and move it to the front.

B Repeatedly swap adjacent elements if they are in the wrong order.

C Use a pivot to partition the list into smaller and larger elements.

D Divide the list into halves and sort each half recursively.

💡 Hint

Think about how selection sort picks elements to place in order.

Selection sort finds the smallest element in the unsorted part and swaps it with the first unsorted element, moving the boundary forward.

❓ Comparison

advanced

Compare Bubble Sort and Selection Sort Behavior

Which of the following is true about bubble sort compared to selection sort?

A Selection sort swaps elements more frequently than bubble sort.

B Bubble sort swaps elements more frequently than selection sort.

C Both algorithms swap elements the same number of times.

D Bubble sort never swaps elements.

💡 Hint

Consider how each algorithm moves elements during sorting.

Bubble sort swaps adjacent elements whenever they are out of order, often many times per pass. Selection sort only swaps once per pass when placing the smallest element.

🔍 Analysis

advanced

Output of Selection Sort Partial Pass

What is the list after the first pass of selection sort on [7, 2, 5, 3]?

Intro to Computing

lst = [7, 2, 5, 3]
min_index = 0
for j in range(1, len(lst)):
    if lst[j] < lst[min_index]:
        min_index = j
lst[0], lst[min_index] = lst[min_index], lst[0]

A [3, 2, 5, 7]

B [7, 2, 5, 3]

C [2, 7, 5, 3]

D [2, 3, 5, 7]

💡 Hint

Selection sort finds the smallest element and swaps it with the first element.

The smallest element is 2 at index 1. It swaps with element at index 0 (7), resulting in [2, 7, 5, 3].

❓ identification

expert

Identify the Algorithm from Behavior

A sorting algorithm repeatedly swaps adjacent elements if they are out of order, and after each full pass, the largest unsorted element moves to its correct position at the end. Which algorithm is this?

A Selection sort

B Merge sort

C Insertion sort

D Bubble sort

💡 Hint

Think about which algorithm moves the largest element to the end each pass by swapping neighbors.

Bubble sort works by swapping adjacent elements and pushing the largest unsorted element to the end after each pass.

Practice

1. Which of the following best describes how bubble sort works?

easy

A. It repeatedly swaps neighboring items to move the largest to the end.

B. It finds the smallest item and places it at the start each time.

C. It divides the list into halves and sorts each half separately.

D. It uses a pivot to partition the list into smaller parts.

Solution

1. Step 1: Understand bubble sort's swapping method

   Bubble sort compares neighbors and swaps them if out of order, pushing the largest to the end.

2. Step 2: Compare with other sorting methods

   Selection sort finds smallest items, quicksort uses pivots, so bubble sort matches It repeatedly swaps neighboring items to move the largest to the end.

3. Final Answer:

   It repeatedly swaps neighboring items to move the largest to the end. -> Option A

4. Quick Check:

   Bubble sort = neighbor swaps [OK]

Hint: Bubble sort swaps neighbors to push largest out [OK]

Common Mistakes:

• Confusing bubble sort with selection sort
• Thinking bubble sort uses pivots
• Assuming bubble sort divides list into halves

2. Which of the following is the correct way to start a selection sort on a list named arr in Python?

easy

A. for i in range(1, len(arr)+1):

B. for i in arr:

C. while i < len(arr):

D. for i in range(len(arr)):

Solution

1. Step 1: Identify the loop for selection sort

   Selection sort uses an index loop from 0 to length-1 to select positions.

2. Step 2: Check Python syntax correctness

   Using for i in range(len(arr)): correctly loops over indices; others are incorrect or off-by-one.

3. Final Answer:

   for i in range(len(arr)): -> Option D

4. Quick Check:

   Selection sort loops over indices 0 to n-1 [OK]

Hint: Use range(len(arr)) to loop over list indices [OK]

Common Mistakes:

• Using for i in arr (loops over values, not indices)
• Using while without initializing i
• Using range starting at 1 causing off-by-one errors

3. What is the output of the following bubble sort pass on the list [4, 2, 5, 1]?

Initial list: [4, 2, 5, 1]
Pass 1: Compare and swap neighbors if needed

medium

A. [2, 4, 5, 1]

B. [2, 4, 1, 5]

C. [4, 2, 1, 5]

D. [1, 2, 4, 5]

Solution

1. Step 1: Perform neighbor comparisons and swaps

   Compare 4 & 2: swap -> [2, 4, 5, 1]; compare 4 & 5: no swap; compare 5 & 1: swap -> [2, 4, 1, 5]

2. Step 2: Confirm final list after pass 1

   After one pass, largest number 5 is bubbled to the end, list is [2, 4, 1, 5]

3. Final Answer:

   [2, 4, 1, 5] -> Option B

4. Quick Check:

   Bubble pass 1 swaps neighbors -> [2, 4, 1, 5] [OK]

Hint: Swap neighbors if left is bigger, largest moves right [OK]

Common Mistakes:

• Not swapping 5 and 1 at the end
• Swapping 4 and 5 incorrectly
• Assuming full sort after one pass

4. The following selection sort code has a bug. What is the error?

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

medium

A. The inner loop should start from i, not i+1

B. The swap line is incorrect; it should not swap

C. No bug; the code correctly sorts the list

D. min_idx should be initialized outside the outer loop

Solution

1. Step 1: Analyze the selection sort logic

   min_idx starts at i, inner loop finds smallest element index after i, then swaps with i.

2. Step 2: Verify correctness with example

   For arr=[3,1,4], code finds min at index 1 and swaps with index 0, resulting in sorted list [1,3,4].

3. Final Answer:

   No bug; the code correctly sorts the list -> Option C

4. Quick Check:

   Selection sort code correct as given [OK]

Hint: Check if code sorts example list correctly [OK]

Common Mistakes:

• Thinking inner loop must start at i
• Believing swap line is wrong
• Misunderstanding min_idx initialization

5. You have a list [7, 3, 5, 2, 9]. After two full passes of selection sort, what will the list look like?

hard

A. [2, 3, 7, 5, 9]

B. [3, 2, 5, 7, 9]

C. [2, 3, 5, 7, 9]

D. [7, 3, 5, 2, 9]

Solution

1. Step 1: Perform first pass of selection sort

   Find smallest in [7, 3, 5, 2, 9] is 2 at index 3; swap with index 0 -> [2, 3, 5, 7, 9]

2. Step 2: Perform second pass on sublist from index 1 [3, 5, 7, 9]

   Find smallest is 3 at index 1; swap with index 1 (no change) -> [2, 3, 5, 7, 9]

3. Final Answer:

   [2, 3, 7, 5, 9] -> Option A

4. Quick Check:

   Selection sort places smallest at start each pass [OK]

Hint: Selection sort fixes one smallest item per pass [OK]

Common Mistakes:

• Assuming list is unchanged after passes
• Mixing bubble sort behavior with selection sort
• Swapping incorrectly during passes