Example 2: Nested for · Selection Sort（選擇排序）

Learning goals（學習目標）

1. Explain what each round of selection sort does: find the smallest, then move it to the front.
2. Tell the two loops apart: the outer i is the round, and the inner j scans.
3. Write the three lines that swap（交換） two numbers.

0. Real-life scene: guess first（生活情境：先猜一猜）

Ten number cards lie on a desk. You want to sort them from smallest to largest. The rule: in each round, check every unsorted card first and remember the smallest. Then swap once.

Guess: After round 1, 12 is at index 0. In round 2, which cards do you check? Which card is the smallest? Which card does it swap with?

中文提示：第 2 輪要在哪幾張卡中找最小？會和誰交換？

1. The task（題目）

Sort the array in ascending order（由小到大）:

Before: 35 52 68 12 47 52 36 52 74 27
After:  12 27 35 36 47 52 52 52 68 74

2. The idea: pick the smallest each round

Split the array into two parts:

• Sorted part（已排序區） on the left, in green. These numbers never move again.
• Unsorted part（未排序區） on the right. Each round searches here for the smallest number.

Each round swaps the smallest number to the first cell of the unsorted part. Ten numbers need only 9 rounds: the last number left must be the largest.

3. Diagrams（圖解）

3.1 Round 1: find first, swap later

Notice: while the inner loop scans, it only remembers the position (minIndex). It swaps once, after the whole scan.

3.2 All 9 rounds

In rounds 5 and 6, the smallest number is already in the right place, so no swap is needed.

4. Code（程式碼）

#include <iostream>
using namespace std;

int main() {
    int data[10] = {35, 52, 68, 12, 47, 52, 36, 52, 74, 27};
    int len = 10;

    for (int i = 0; i < len - 1; i++) {          // round i: decide what goes in cell i
        int minIndex = i;                        // assume cell i is the smallest
        for (int j = i + 1; j < len; j++) {      // scan the unsorted part
            if (data[j] < data[minIndex]) {
                minIndex = j;
            }
        }
        int temp = data[i];                      // swap the smallest into cell i
        data[i] = data[minIndex];
        data[minIndex] = temp;
    }

    for (int i = 0; i < len; i++) cout << data[i] << " ";
    cout << endl;
    return 0;
}

5. Key lines（重點逐行看）

Why do we need temp to swap?

Think of swapping the drinks in two cups. You need an empty third cup.

Without temp, writing data[i] = data[minIndex] first makes 35 disappear.

6. The shape of nested for loops（雙層 for 的形狀）

Each round does one fewer comparison, so n numbers need n(n-1)/2 comparisons. For 10 numbers that is 45.

7. Common mistakes（常見錯誤）

• Starting the inner loop at j = 0. It scans the sorted part and moves numbers that are already in place.（內層不可由 0 開始）
• Swapping inside the inner loop. That swaps every time a smaller number appears. It does many more swaps and is no longer selection sort.
• Storing the value instead of the index in minIndex. Then you do not know which cell to swap with.

ClassWork 2-1: Largest to smallest（由大到小）

Change one symbol and one variable name, and the program sorts from largest to smallest.

Task: Read n integers. Use selection sort to sort them in descending order（由大到小）, then print them.

Input format（輸入格式）

• Line 1: an integer n (1 ≤ n ≤ 100)
• Line 2: n integers (they may be negative)

Output format（輸出格式）: one line with the sorted numbers, separated by one space.

Sample 1

Input:

10
35 52 68 12 47 52 36 52 74 27

Output:

74 68 52 52 52 47 36 35 27 12

Sample 2

Input:

4
3 -1 8 0

Output:

8 3 0 -1

Hints（提示）

• Largest to smallest means: each round, find the largest number and move it to the front.
• Rename minIndex to maxIndex so the code is easier to read.

ClassWork 2-2: Print every round（印出每一輪）

Print the whole array after every round. Use it to check your trace on paper.

Task: Read n integers and sort them in ascending order with selection sort. After the swap in each round, print the whole array once (n - 1 lines in total).

中文提示：每一輪交換之後印出整個陣列，一共 n − 1 行。

Input format（輸入格式）

• Line 1: an integer n (2 ≤ n ≤ 100)
• Line 2: n integers

Output format（輸出格式）: n - 1 lines. Each line is the array after that round, separated by one space.

Sample 1

Input:

5
29 10 14 37 13

Output:

10 29 14 37 13
10 13 14 37 29
10 13 14 37 29
10 13 14 29 37

Hints（提示）

• The loop that prints the array goes inside the outer loop, after the swap.
• In round 3 the smallest number, 14, is already in place. It swaps with itself and the array does not change, but you still print it.
• Trace the sample on paper first, then write the program.

Self-check（自我檢查）

1. With 10 numbers, how many rounds does the outer loop run? How many comparisons are there in total?
2. Why does the inner loop start at i + 1 and not at 0?
3. Without looking at the code, write the three lines that swap a and b.

Learning notes: Excerpt and Comment → Note Card（學習筆記：節錄評論法 → 卡片盒）

Reading is not the same as learning. Use Excerpt and Comment（節錄評論法）: copy one key sentence, then add your own experience and ideas. Write the result as a note card（卡片盒筆記）. Each card holds one idea, so you can link cards together later.

Step 1: Excerpt one key sentence（節錄一句重點）

"While the inner loop scans, it only remembers the position. It swaps once, after the whole scan."

Step 2: Answer the guiding questions（回答引導提問）

Choose one option, then add one or two sentences of your own.

Question 1 · Why it stopped you（共鳴探索）: Why did this sentence make you stop and think?

• A. When I code, I often swap as soon as I see a smaller number
• B. It reminds me of "look at everything first, then decide" when I line up or choose something
• C. I finally understand why minIndex stores a position, not a value
• D. Something else (tell us)

Question 2 · Challenge it（觀點質疑）: Is there anything about selection sort you do not fully agree with?

• A. If the data is already sorted, it still makes 45 comparisons. That seems wasteful.
• B. It swaps only once per round, but it does not make fewer comparisons.
• C. With 1,000 numbers it needs almost 500,000 comparisons. Is that too slow?
• D. Something else (tell us)
• E. I agree completely. Ask a classmate or the teacher to argue against me.

Step 3: Write your card（寫成你的卡片）

Write three parts in this order: Viewpoint → Case → Conclusion（觀點 → 案例 → 總結）. Use your own words, about 100 to 180 words.

Card title (8 to 15 words; state your conclusion; not a question):

Viewpoint (2 to 3 sentences): Your first sentence states what you learned.

Case (3 to 5 sentences): Your own experience. You may add a question or
something you do not agree with.

Conclusion (1 to 2 sentences): One small action for this week,
for example "This week, when I code, I will ...".

🔗 Related notes to write next (2 to 3 directions):
→ Topic: "Title"
→ Topic: "Title"

Check: Can the title be understood on its own? Is the case your own experience, not copied from these notes? Does the conclusion give a concrete action for this week?

中文提示：卡片可以用中文寫（約 150 到 250 字）；標題直接講結論，案例要有自己的經驗。

Sample card（示範卡）

Card | Selection sort checks everything first, then swaps once

Each round of selection sort does only two things. First it looks at every unsorted number and remembers where the smallest one is. Then, after the scan, it swaps once. So each round swaps at most once, and the sorted part on the left never moves again.

It reminds me of how our PE teacher lines us up. He looks at the whole class, calls the shortest student to the front, then looks for the next one among the rest. When I first wrote this program, I swapped every time I saw a smaller number. I made many swaps, and it was not selection sort. I still have a question: if the data is already sorted, selection sort still makes 45 comparisons, which seems wasteful.

Before I write my next nested loop, I will mark on paper that the scan goes in the inner loop and the swap goes in the outer loop.

🔗 Related notes:

→ Efficiency: "Comparisons tell you more about speed than swaps do"

→ Coding: "Always use temp before you swap two numbers"

→ Daily life: "Look at every option first, and you will regret less"