Sorting algorithms (bubble, selection) in Intro to Computing - Flowchart & Logic Diagram

Process Overview

Sorting algorithms arrange items in order. Bubble sort swaps neighbors to push the largest to the end. Selection sort finds the smallest and places it at the start. Both repeat until sorted.

Flowchart

Set i = 0

|Yes↓

Set j = 0

|Yes↓

j

↓

Swap arr[j

|No↓

Increment j

(Loop back to j < n-1-i?)↓

Increment i

(Loop back to i < n-1?)↓

Set i = 0

|Yes↓

Set min_index = i

↓

Set j = i+1

|Yes↓

j

↓

Set min_index = j

|No↓

Increment j

(Loop back to j < n?)↓

Swap arr[i

|No↓

Increment i

↩(Loop back to j < n-1-i?)

This flowchart shows the step-by-step process of bubble sort and selection sort algorithms for sorting an array.

Step-by-Step Trace - 33 Steps

Step 1: Start bubble sort with array [4, 2, 5, 1]

Step 2: Compare arr[0]=4 and arr[1]=2

Step 3: Swap 4 and 2 because 4 > 2

Step 4: Compare arr[1]=4 and arr[2]=5

Step 5: Compare arr[2]=5 and arr[3]=1

Step 6: Swap 5 and 1

Step 7: Increment i to 1, start next pass

Step 8: Compare arr[0]=2 and arr[1]=4

Step 9: Compare arr[1]=4 and arr[2]=1

Step 10: Swap 4 and 1

Step 11: Increment i to 2, start next pass

Step 12: Compare arr[0]=2 and arr[1]=1

Step 13: Swap 2 and 1

Step 14: End bubble sort

Step 15: Start selection sort with array [4, 2, 5, 1]

Step 16: Set min_index = 0 (value 4)

Step 17: Compare arr[1]=2 with arr[min_index]=4

Step 18: Set min_index = 1

Step 19: Compare arr[2]=5 with arr[min_index]=2

Step 20: Compare arr[3]=1 with arr[min_index]=2

Step 21: Set min_index = 3

Step 22: Swap arr[0]=4 and arr[3]=1

Step 23: Increment i to 1

Step 24: Set min_index = 1 (value 2)

Step 25: Compare arr[2]=5 with arr[min_index]=2

Step 26: Compare arr[3]=4 with arr[min_index]=2

Step 27: min_index = i, no swap needed

Step 28: Increment i to 2

Step 29: Set min_index = 2 (value 5)

Step 30: Compare arr[3]=4 with arr[min_index]=5

Step 31: Swap arr[2]=5 and arr[3]=4

Step 32: Increment i to 3

Step 33: End selection sort

Diagram

Array Memory Layout:

Index:  0    1    2    3
       +----+----+----+----+
Value: | 4  | 2  | 5  | 1  |
       +----+----+----+----+

During sorting, values swap places in these boxes.

Bubble Sort pushes largest values to the right step by step.
Selection Sort picks smallest values and places them at the left step by step.

This diagram shows the array as boxes in memory with indexes and values. It helps visualize how sorting swaps values in place.

Flowchart Quiz - 3 Questions

In bubble sort, what happens when two adjacent elements are compared and the left one is larger?

A The smaller element moves left

B They are left as is

C They are swapped to move the larger element right

D The algorithm ends

Key Result

Both bubble and selection sort repeatedly compare and swap elements to gradually arrange the array in order, but bubble sort swaps neighbors while selection sort swaps the smallest found element with the current position.

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