I. In-Class Exercises

Programming Exercises

1. Bubble Sort: L2151
2. Absolute Value Sort: L2152

II. Knowledge Summary

Bubble Sort: Core Concept

Sort a collection of data stored in a linear structure.

Bubble Sort works by repeatedly comparing the sizes of adjacent elements and swapping those that are in the wrong order. Each pass through the array "bubbles" the extreme value of the unsorted portion to the end. Bubble Sort is a sorting algorithm that uses the Greedy Algorithm approach.

How Bubble Sort Works

Bubble Sort follows these steps:

1. Initialize: Mark the sorted portion as empty
2. Traverse the unsorted portion starting from the first element:
   • Compare each pair of adjacent elements
   • Swap the two elements if they are in the wrong order
3. Update the sorted portion (after each pass, the last element is in place)
4. Repeat steps 2-3 until all elements are sorted

Bubble Sort can be optimized by using a flag variable: if no swaps occur during a pass, the array is already sorted and the algorithm can terminate early.

Ascending Order (Small to Large)

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1005] = {};
5
6int main() {
7        int n;
8        cin >> n;
9        for (int i = 0; i < n; ++i) {
10                cin >> arr[i];
11        }
12        for (int i = 0; i < n - 1; ++i) {
13                bool flag = true;
14                for (int j = 0; j < n - 1 - i; ++j) {
15                        if (arr[j] > arr[j + 1]) {
16                                swap(arr[j], arr[j + 1]);
17                                flag = false;
18                        }
19                }
20                if (flag) {
21                        break;
22                }
23        }
24    for (int i = 0; i < n; ++i) {
25            cout << arr[i] << (i + 1 == n ? "\n" : " ");
26    }
27    return 0;
28}

Descending Order (Large to Small)

Simply change the comparison from > to <, moving smaller elements toward the end each time:

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1005] = {};
5
6int main() {
7        int n;
8        cin >> n;
9        for (int i = 0; i < n; ++i) {
10                cin >> arr[i];
11        }
12        for (int i = 0; i < n - 1; ++i) {
13                bool flag = true;
14                for (int j = 0; j < n - 1 - i; ++j) {
15                        if (arr[j] < arr[j + 1]) {
16                                swap(arr[j], arr[j + 1]);
17                                flag = false;
18                        }
19                }
20                if (flag) {
21                        break;
22                }
23        }
24    for (int i = 0; i < n; ++i) {
25            cout << arr[i] << (i + 1 == n ? "\n" : " ");
26    }
27    return 0;
28}

Complexity Analysis of Bubble Sort

Bubble Sort has a time complexity of O(n^2) because it requires two nested loops. The space complexity is O(1), requiring only constant extra space for swapping. Bubble Sort is a stable sorting algorithm because it only swaps elements when one is strictly greater than (or less than) the other, so the relative order of equal elements is preserved.

Execution Example of Bubble Sort

Using the array [5, 3, 8, 1, 2] as an example, here is the complete ascending Bubble Sort process:

Round 1 (i=0): 4 comparisons, "bubble" the maximum to the end

End of Round 1: 8 has reached its correct position -> [3, 5, 1, 2, 8]

Round 2 (i=1): 3 comparisons

End of Round 2: 5 has reached its correct position -> [3, 1, 2, 5, 8]

Round 3 (i=2): 2 comparisons

End of Round 3: 3 has reached its correct position -> [1, 2, 3, 5, 8]

Round 4 (i=3): 1 comparison

No swaps occurred, flag remains true, terminate early.

Sorting complete: [1, 2, 3, 5, 8]

Observations:

• Round k makes n-1-k comparisons (because the last k elements are already sorted)
• After each round, the maximum of the unsorted portion has "bubbled" to the rightmost position

Problem-Solving Steps with Bubble Sort

Example: Sort by Date

Given several dates (year/month/day), sort them in chronological order.

Analysis:

1. Choose a sorting algorithm: Bubble Sort can accomplish this task
2. Design the comparison rule: Compare year first, then month if years are equal, then day if months are equal
3. Modify the Bubble Sort comparison condition:

1struct Date {
2    int year, month, day;
3};
4
5// Check if date a should come after date b (a is later than b)
6bool isLater(Date a, Date b) {
7    if (a.year != b.year) return a.year > b.year;
8    if (a.month != b.month) return a.month > b.month;
9    return a.day > b.day;
10}
11
12// Bubble Sort
13for (int i = 0; i < n - 1; ++i) {
14    bool flag = true;
15    for (int j = 0; j < n - 1 - i; ++j) {
16        if (isLater(dates[j], dates[j + 1])) {
17            swap(dates[j], dates[j + 1]);
18            flag = false;
19        }
20    }
21    if (flag) break;
22}

Key insight: Bubble Sort only cares about "which of two adjacent elements should come first." Encapsulate complex comparison logic in a function, and the sorting framework stays unchanged.

Common Mistakes in Bubble Sort

1. Wrong upper bound for the inner loop: It should be j < n - 1 - i, not j < n - 1 or j < n. Using j < n - 1 gives correct results but performs unnecessary comparisons each round; using j < n causes arr[j+1] to go out of bounds
2. Reversed comparison condition: For ascending sort, swap when arr[j] > arr[j+1]; writing < instead would produce descending order
3. Misplaced flag optimization: The flag should be reset to true at the start of each round and set to false upon swapping. If initialized outside the loop, it can only optimize the first round
4. Swapping on equality: The comparison should use strict greater-than >, not >=. Using >= would swap equal elements, breaking Bubble Sort's stability
5. Assuming Bubble Sort always needs n-1 rounds: With the flag optimization, if the data is already sorted, no swaps occur in the first round and the algorithm can terminate immediately

III. Homework

Programming Exercises

1. Odd Number Ascending Sequence: L2153
2. Date Sorting: L2154