Example 3: Nested for · Bubble Sort（冒泡排序）

Learning goals（學習目標）

1. Explain each step of bubble sort: compare two neighbours; if the left one is bigger, swap.
2. Explain why the inner loop is j < len - i - 1.
3. Compare bubble sort with selection sort.

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

Ten students stand in a line. The number on each student is their height. The rule: you may only compare two neighbours. If the left student is taller, they swap places. Walking once from left to right is one round.

Guess: After 68 and 12 swap, which two students does j = 3 compare? Do they swap? Who stands at the end after round 1?

中文提示：68 和 12 交換後，j = 3 比較哪兩位？第 1 輪結束誰站最後？

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: big numbers bubble up（像泡泡一樣浮上去）

• Each step looks only at two neighbours, data[j] and data[j+1].
• If the left one is bigger, swap them.
• After one round, the largest unsorted number is always at the right end.
• So after each round, one more cell on the right is sorted, and the next round can compare one cell fewer.

3. Diagrams（圖解）

3.1 Round 1: compare neighbours

Follow 68: from j = 2 it is swapped to the right step by step until it meets the bigger 74. Then 74 keeps moving right, swaps with 27, and reaches the last cell.

3.2 All 9 rounds

The small number 27 starts at the right end. It can move only one cell to the left per round, so it is not in place until round 8.

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++) {          // len - 1 rounds in total
        for (int j = 0; j < len - i - 1; j++) {  // one fewer each round: the last i cells are sorted
            if (data[j] > data[j + 1]) {         // left is bigger → swap
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }

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

5. Key lines（重點逐行看）

Why j < len - i - 1?

There is also a - 1. The code reads data[j + 1], so j can go only up to the second-to-last cell. Otherwise data[j + 1] would be outside the array.

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

7. Bubble sort vs selection sort（比較）

8. Common mistakes（常見錯誤）

• Writing the inner loop as j < len. The last step reads data[10], which is outside the array.
• Comparing data[j] > data[i]. Bubble sort compares neighbours: j and j + 1.（比較的是相鄰兩格）
• Thinking one round sorts everything. One round only puts the largest number at the end.

ClassWork 3-1: Count the swaps（數一數交換次數）

Add a counter inside the if statement.

Task: Read n integers and sort them in ascending order with bubble sort. Print the sorted numbers, then print how many swaps were made.

Input format（輸入格式）

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

Output format（輸出格式）

• Line 1: the sorted numbers, separated by one space
• Line 2: the number of swaps

Sample 1

Input:

5
5 1 4 2 8

Output:

1 2 4 5 8
4

Sample 2

Input:

10
35 52 68 12 47 52 36 52 74 27

Output:

12 27 35 36 47 52 52 52 68 74
19

Hints（提示）

• Put swaps++ inside the if statement: add 1 only when a swap really happens.
• Check Sample 2 against diagram 3.2: 6 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 0 = 19.

ClassWork 3-2: Stop early（提早停止）

If a whole round makes no swaps, the array is already sorted, so you can break.

Task: Read n integers and sort them in ascending order with bubble sort. If a round makes no swaps at all, stop at once. Print the sorted numbers, then print how many rounds were actually run. The round with no swaps also counts.

中文提示：某一輪完全沒有交換就立即停止；沒有交換的那一輪也要計算。

Input format（輸入格式）

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

Output format（輸出格式）

• Line 1: the sorted numbers, separated by one space
• Line 2: the number of rounds actually run

Sample 1

Input:

5
1 2 3 5 4

Output:

1 2 3 4 5
2

Sample 2

Input:

5
1 2 3 4 5

Output:

1 2 3 4 5
1

Sample 3

Input:

5
5 4 3 2 1

Output:

1 2 3 4 5
4

Hints（提示）

• At the start of each round, set bool swapped = false;. When the if statement swaps, set it to true.
• After the inner loop, check: if (!swapped) break;
• Sample 1: round 1 swaps 5 and 4; round 2 makes no swaps, so stop. 2 rounds in total.
• Sample 3: every round swaps, so it runs the maximum of n - 1 = 4 rounds.

Self-check（自我檢查）

1. After round 1 of bubble sort, which number is certainly in its final place?
2. Explain the - i and the - 1 in j < len - i - 1.
3. For an array that is already sorted, how many rounds does ClassWork 3-2 run? How many does the original program run?

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（節錄一句重點）

"One round only puts the largest number at the end. The small 27 moves left only one cell per round."

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

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

Question 1 · Challenge it（觀點質疑）: Someone says, "Bubble sort is better than selection sort." Do you agree?

• A. Yes, because bubble sort can stop early (ClassWork 3-2)
• B. No. On the same data it made 19 swaps; selection sort made only 7
• C. It depends on the data: bubble sort is better when the data is almost sorted
• D. Something else (tell us)

Question 2 · Experience link（經驗連結）: "You may only swap with your neighbour." What experience does this remind you of?

• A. Lining up by height in PE or at assembly
• B. Moving books, cards or stationery into order one step at a time
• C. Comparing two at a time and knocking one out in a game
• D. Something else (tell us)

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 | One round of bubble sort only puts the largest number last

Each step of bubble sort compares two neighbours and swaps them if the left one is bigger. After one round, only the largest number is sure to be at the end. Other numbers may have moved just one cell. That is why the inner loop is j < len - i - 1, with one comparison fewer each round.

Our class once tried lining up by height, and we could only swap with the person next to us. The tallest student reached the end quickly, but the shortest student moved forward just one place per round, and it took a long time. The 27 in the diagram is the same: it is not in place until round 8. I used to think bubble sort was faster than selection sort, but on the same data it made 19 swaps, and selection sort made only 7.

This week, in ClassWork 3-2, I will add a swapped variable to see from which round the array is already sorted.

🔗 Related notes:

→ Better sorting: "Insertion sort is very fast when data is almost sorted"

→ Program design: "A bool variable can end a loop early"

→ Learning methods: "Acting out an algorithm is easier to remember than reading code"