I. In-Class Exercises

Programming Exercises

1. Selection Sort: L2131
2. Selection Sort with Position Output: L2132

II. Knowledge Summary

Selection Sort: Core Concept

Sort a collection of data stored in a linear structure.

Selection Sort works by repeatedly selecting the extreme value (minimum or maximum) from the unsorted portion and placing it at the end of the sorted portion. Selection Sort is a sorting algorithm that uses the Greedy Algorithm approach -- each step selects the current optimal element and places it in the correct position.

How Selection Sort Works

Selection Sort follows these steps:

1. Initialize: Mark the sorted portion as empty
2. Find the extreme value in the unsorted portion (minimum for ascending, maximum for descending)
3. Swap the extreme value with the first element of the unsorted portion
4. Update the sorted portion (one more element is now sorted)
5. Repeat steps 2-4 until all elements are sorted

Ascending Order (Small to Large)

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1003] = {};
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                int min_idx = i;
14                for (int j = i + 1; j < n; ++j) {
15                        if (arr[j] < arr[min_idx]) {
16                                min_idx = j;
17                        }
18                }
19                swap(arr[i], arr[min_idx]);
20        }
21        for (int i = 0; i < n; ++i) {
22                cout << arr[i] << (i + 1 == n ? "\n" : " ");
23        }
24    return 0;
25}

Descending Order (Large to Small)

Simply change the comparison from < to >, selecting the maximum value from the unsorted portion each time:

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1003] = {};
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                int max_idx = i;
14                for (int j = i + 1; j < n; ++j) {
15                        if (arr[j] > arr[max_idx]) {
16                                max_idx = j;
17                        }
18                }
19                swap(arr[i], arr[max_idx]);
20        }
21        for (int i = 0; i < n; ++i) {
22                cout << arr[i] << (i + 1 == n ? "\n" : " ");
23        }
24    return 0;
25}

Complexity Analysis of Selection Sort

Selection 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. Selection Sort is an unstable sorting algorithm because the swap operation may change the relative order of equal elements.

Execution Example of Selection Sort

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

Round 1 (i=0): Find the minimum in [5, 3, 8, 1, 2]

Swap arr[0] and arr[3]: [1, 3, 8, 5, 2] (1 is in place)

Round 2 (i=1): Find the minimum in [3, 8, 5, 2]

Swap arr[1] and arr[4]: [1, 2, 8, 5, 3] (2 is in place)

Round 3 (i=2): Find the minimum in [8, 5, 3]

Found minimum 3 at position 4, swap arr[2] and arr[4]: [1, 2, 3, 5, 8] (3 is in place)

Round 4 (i=3): Find the minimum in [5, 8]

Found minimum 5 at position 3 (already the current position), no swap needed: [1, 2, 3, 5, 8] (5 is in place)

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

Summary: 5 elements require 4 rounds of selection; n elements require n-1 rounds.

Problem-Solving Steps with Selection Sort

Example: Rank students by score, with ties broken by student ID

Analysis:

1. The basic framework of Selection Sort stays the same: outer loop for n-1 rounds, inner loop to find the extreme value
2. Modify the comparison condition: compare not only scores but also student IDs when scores are equal
3. Use a struct to store data: each element contains both a student ID and a score

1struct Student {
2    int id, score;
3};
4
5Student stu[1005];
6
7// Selection Sort: scores descending, same score sorted by ID ascending
8for (int i = 0; i < n - 1; ++i) {
9    int best = i;
10    for (int j = i + 1; j < n; ++j) {
11        if (stu[j].score > stu[best].score ||
12            (stu[j].score == stu[best].score && stu[j].id < stu[best].id)) {
13            best = j;
14        }
15    }
16    swap(stu[i], stu[best]);
17}

Key insight: The core of Selection Sort is simply "find the extreme value and swap." By modifying the comparison condition, you can adapt it to different sorting requirements.

Common Mistakes in Selection Sort

1. Wrong starting position for the inner loop: The inner loop should start from i+1, not from 0. Starting from 0 would redundantly compare already-sorted elements -- the result is correct but wastes time
2. Forgetting to track the position of the minimum: Swapping directly inside the loop each time a smaller value is found increases the number of unnecessary swaps
3. Swapping an element with itself: When the minimum is already at position i, swap(arr[i], arr[i]) won't cause an error, but you can add an if (min_idx != i) check to avoid the redundant operation
4. Wrong number of outer loop iterations: For n elements, only n-1 rounds are needed. Writing i < n would cause the inner loop's j = i+1 to go out of bounds (it may not crash but is logically incorrect)
5. Assuming Selection Sort is stable: Selection Sort is unstable. For example, with [5a, 5b, 3], the first round swaps 5a with 3, resulting in [3, 5b, 5a] -- the relative order of the two 5s has changed

III. Homework

Programming Exercises

1. Number Sorting: L2133
2. Dictionary Sort: L2134