I. In-Class Exercises

Programming Exercises

1. Insertion Sort: L2161
2. 01 String Sort: L2162

II. Knowledge Summary

Insertion Sort: Core Concept

Sort a collection of data stored in a linear structure.

Insertion Sort builds an ordered sequence by inserting elements one at a time. It works just like organizing cards in your hand -- each time you pick up a new card, you insert it into the correct position among the cards already sorted. Insertion Sort is a sorting algorithm that uses the Greedy Algorithm approach.

How Insertion Sort Works

Insertion Sort follows these steps:

1. Initialize: Treat the first element as the sorted portion
2. Take the first element X from the unsorted portion
3. Scan the sorted portion from right to left to find the first element Y that is not greater than X:
   • If Y exists, insert X after Y
   • Otherwise, insert X before all elements
4. Repeat steps 2-3 until all elements are sorted

In implementation, elements greater than X are shifted right one by one to make room for the insertion, avoiding explicit insert operations.

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 = 1; i < n; ++i) {
13                int key = arr[i];
14                int j = i - 1;
15                while (j >= 0 && key < arr[j]) {
16                        arr[j + 1] = arr[j];
17                        --j;
18                }
19                arr[j + 1] = key;
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 >, shifting smaller elements to the right 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 = 1; i < n; ++i) {
13                int key = arr[i];
14                int j = i - 1;
15                while (j >= 0 && key > arr[j]) {
16                        arr[j + 1] = arr[j];
17                        --j;
18                }
19                arr[j + 1] = key;
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 Insertion Sort

Insertion Sort has a time complexity of O(n^2) because in the worst case, each element must be compared with all preceding elements. The space complexity is O(1), requiring only constant extra space. Insertion Sort is a stable sorting algorithm because equal elements are never swapped. For nearly sorted data, Insertion Sort's efficiency approaches O(n), outperforming Selection Sort and Bubble Sort.

Execution Example of Insertion Sort

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

Initial State

Sorted portion: [5], Unsorted portion: [3, 8, 1, 2]

Round 1 (i=1): Insert key=3

Sorted: [3, 5], Unsorted: [8, 1, 2]

Round 2 (i=2): Insert key=8

Sorted: [3, 5, 8], Unsorted: [1, 2]

Round 3 (i=3): Insert key=1

Sorted: [1, 3, 5, 8], Unsorted: [2]

Round 4 (i=4): Insert key=2

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

Observations:

• Each round takes one element and finds the right position in the sorted portion by scanning from right to left
• If the element to insert is already larger than all preceding elements, no shifting is needed and it stays in place (like 8 in Round 2)
• If the data is nearly sorted, most elements need only a few comparisons to find their position, making the algorithm very efficient

Problem-Solving Steps with Insertion Sort

Example: Insert a new element into an already sorted array while maintaining order

This is a direct application of a single round of Insertion Sort.

Example: Given the sorted array [1, 3, 5, 7, 9], insert element 4.

Solution steps:

1. Save the element to insert: key = 4
2. Scan from right to left, find the first element not greater than key:
   • arr[4]=9 > 4, shift right -> [1, 3, 5, 7, , 9] ( marks the vacated position)
   • arr[3]=7 > 4, shift right -> [1, 3, 5, _, 7, 9]
   • arr[2]=5 > 4, shift right -> [1, 3, _, 5, 7, 9]
   • arr[1]=3 <= 4, stop
3. Insert at position 2: [1, 3, 4, 5, 7, 9]

1// Insert key into sorted array arr[0..n-1], array length becomes n+1
2void insertSorted(int arr[], int &n, int key) {
3    int j = n - 1;
4    while (j >= 0 && key < arr[j]) {
5        arr[j + 1] = arr[j];
6        --j;
7    }
8    arr[j + 1] = key;
9    ++n;
10}

Common Mistakes in Insertion Sort

1. Wrong shift direction: When inserting, scan from right to left and shift elements to the right that are greater than key. Shifting from left to right would overwrite and lose data
2. Forgetting to save key: You must save the element to insert with int key = arr[i] before shifting, otherwise arr[i] will be overwritten by the shifted element
3. Missing boundary check in the while loop: The j >= 0 condition in while (j >= 0 && key < arr[j]) cannot be omitted -- when key is the smallest value, j would become -1, causing an array out-of-bounds access
4. Using <= instead of < for comparison: Shift only when key < arr[j]. Using key <= arr[j] would also shift equal elements, changing the relative order of equal values and breaking stability
5. Starting the outer loop from i=0: It should start from i=1 because the first element is already sorted by itself and does not need to be inserted

III. Homework

Programming Exercises

1. Find Unique Elements and Sort: L2163
2. Student Team Formation: L2164