Sorting algorithms (bubble, selection) in Intro to Computing - Full Explanation

Introduction

Imagine you have a messy pile of books and want to arrange them from shortest to tallest. Sorting algorithms help computers organize data in a specific order, making it easier to find or use later.

Explanation

Bubble Sort

Bubble sort works by repeatedly stepping through the list, comparing pairs of items next to each other. If a pair is in the wrong order, it swaps them. This process repeats until no more swaps are needed, meaning the list is sorted.

Bubble sort sorts by swapping adjacent items repeatedly until the whole list is ordered.

Selection Sort

Selection sort divides the list into a sorted part and an unsorted part. It repeatedly finds the smallest item in the unsorted part and moves it to the front of the sorted part. This continues until all items are sorted.

Selection sort sorts by repeatedly selecting the smallest remaining item and placing it in order.

Real World Analogy

Imagine lining up students by height. Bubble sort is like students comparing heights with their neighbor and swapping places if needed, passing through the line many times. Selection sort is like picking the shortest student from the group and placing them at the front one by one.

Bubble Sort → Students comparing heights with their neighbor and swapping places repeatedly

Selection Sort → Picking the shortest student from the group and placing them at the front one by one

Diagram

Diagram

Unsorted List: 5 3 8 4 2

Bubble Sort Passes:
Pass 1: 3 5 4 2 8
Pass 2: 3 4 2 5 8
Pass 3: 3 2 4 5 8
Pass 4: 2 3 4 5 8

Selection Sort Steps:
Step 1: Find min (2), swap with first (5) → 2 3 8 4 5
Step 2: Find min (3), already in place → 2 3 8 4 5
Step 3: Find min (4), swap with third (8) → 2 3 4 8 5
Step 4: Find min (5), swap with fourth (8) → 2 3 4 5 8
Step 5: Last item sorted → 2 3 4 5 8

This diagram shows step-by-step how bubble sort swaps adjacent items and how selection sort picks the smallest item to place in order.

Key Facts

Bubble Sort → A simple sorting method that swaps adjacent items repeatedly until sorted.

Selection Sort → A sorting method that selects the smallest item from unsorted data and moves it to the sorted part.

Swap → Exchanging the positions of two items in a list.

Sorted Part → The portion of the list that is already arranged in order.

Unsorted Part → The portion of the list that still needs to be arranged.

Common Confusions

Thinking bubble sort compares items far apart, not just neighbors.

Thinking bubble sort compares items far apart, not just neighbors. Bubble sort only compares and swaps adjacent items in each pass.

Believing selection sort swaps items every time it looks at them.

Believing selection sort swaps items every time it looks at them. Selection sort only swaps once per pass after finding the smallest item.

Summary

Bubble sort organizes a list by swapping neighbors repeatedly until sorted.

Selection sort organizes a list by repeatedly picking the smallest item and placing it in order.

Both methods help computers arrange data but work in different ways.

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