I. In-Class Exercises

Programming Exercises

1. Selection Sort: L2131
2. Bubble Sort: L2151
3. ID Card Sort: L2181
4. Integer Odd-Even Sort: L2182
5. Grade Sort: L2183

II. Knowledge Summary

The sort Function: Core Concept

In C++, the sort function can be used to sort data stored in a linear structure. By default, sort arranges data in ascending order. To customize the sorting rule, you can provide a custom cmp function.

Using the sort function requires the std namespace (or using namespace std).

Basic usage for sorting an array arr of n elements:

sort(arr, arr + n); // Sort in ascending order
sort(arr, arr + n, cmp); // Sort using a custom cmp function

The first two parameters of sort are the start address and the end address of the sorting range (a half-open interval), and the optional third parameter is a custom comparison function.

The cmp Function

The cmp function used with sort takes two parameters and returns a boolean value. For parameters a and b, if cmp(a, b) returns true, then a should be placed before b.

Here is an example of a cmp function for descending order:

bool cmp(int a, int b) {
    return a > b;
}

When a > b returns true, it means the larger number comes first, achieving descending order. By writing different cmp functions, you can flexibly implement various custom sorting rules, such as sorting by absolute value, sorting by a specific field of a struct, etc.

Execution Examples of the sort Function

Below are concrete examples demonstrating the use of the sort function.

Example 1: Basic sorting

Input array: arr = [5, 2, 8, 1, 9, 3], n = 6
Call: sort(arr, arr + 6);
After sorting: arr = [1, 2, 3, 5, 8, 9]

Example 2: Descending order using a cmp function

bool cmp(int a, int b) {
    return a > b;  // a > b means a comes first, i.e., descending
}

sort(arr, arr + 6, cmp);

Before sorting: arr = [5, 2, 8, 1, 9, 3]
After sorting: arr = [9, 8, 5, 3, 2, 1]

Example 3: Struct sorting -- by score descending, then by name in lexicographic ascending order for ties

1struct Student {
2    string name;
3    int score;
4};
5
6bool cmp(Student a, Student b) {
7    if (a.score != b.score) {
8        return a.score > b.score;  // Higher score comes first
9    }
10    return a.name < b.name;  // Same score, smaller name comes first
11}

Before sorting: [("Bob",90), ("Alice",95), ("Charlie",90), ("David",85)]
After sorting: [("Alice",95), ("Bob",90), ("Charlie",90), ("David",85)]

Bob and Charlie have the same score, so they are sorted by name in lexicographic order -- Bob comes before Charlie.

Example 4: Sorting a subarray

Array: arr = [5, 2, 8, 1, 9, 3]
Sort only indices 1~4: sort(arr + 1, arr + 5);
After sorting: arr = [5, 1, 2, 8, 9, 3]

The sorting range of sort is a half-open interval: arr + 1 is the start (inclusive) and arr + 5 is the end (exclusive), so elements arr[1] through arr[4] are sorted.

Problem-Solving Steps with the sort Function

General steps for solving sorting problems with sort:

1. Analyze the sorting rule: Read the problem carefully to determine the sorting criteria (ascending/descending/multi-key)
2. Determine the data structure: For multi-key sorting, you usually need to define a struct to store multiple fields
3. Write the cmp function: Based on the sorting rule, write the comparison function -- remember that return true means the first parameter should come first
4. Determine the sorting range: Identify the start and end addresses for sort -- remember it is a half-open interval
5. Call sort and output: Call sort and then output the result as required

Template for multi-key cmp functions:

1bool cmp(Type a, Type b) {
2    if (a.firstKey != b.firstKey) {
3        return a.firstKey > b.firstKey;  // First key descending
4    }
5    return a.secondKey < b.secondKey;  // Second key ascending
6}

Common Mistakes with the sort Function

1. Using >= or <= in the cmp function: The cmp function must return false when two elements are equal, otherwise sort may enter an infinite loop or crash. For example, return a >= b; is incorrect -- use return a > b; instead
2. Wrong sorting range: sort(arr, arr + n) sorts arr[0] through arr[n-1]. Writing sort(arr, arr + n - 1) would miss the last element
3. Mismatched parameter types in cmp: The parameter types of the cmp function must match the array element type. When sorting an int array, parameters should be int; when sorting a struct array, parameters should be the struct type
4. Forgetting to handle the equality case: In multi-key sorting, you must first check whether the current key differs. Only sort by the current key when it differs; proceed to the next key comparison only when they are equal
5. Inefficient struct parameter passing: When the struct is large, the cmp function parameters should use const Student &a (pass by reference) to avoid unnecessary copies

III. Homework

Programming Exercises

1. Largest Number from n Single Digits: L2184
2. Ranking with Ties: L2185