I. In-Class Exercises

Programming Exercises

1. Array Sorting: L3121

II. Knowledge Summary

✨ Core Idea

Quick Sort is used to sort a collection of linearly stored data and is one of the most commonly used sorting algorithms in practice.

The core idea of quick sort is Divide and Conquer. It uses an element called the pivot to partition the array into two subarrays. Elements smaller than the pivot go to one side, and elements larger than the pivot go to the other side. This process is called the partition operation. Then, the same method is recursively applied to the two subarrays until the array size is reduced to 1.

✨ Algorithm Principle

The main steps of quick sort include:

1. Choose a pivot: Select an element from the array as the pivot point. Common methods include random selection, choosing the first element, or choosing the last element. The choice of pivot affects the algorithm's performance.
2. Partition operation: Rearrange the array so that all elements smaller than the pivot are moved to the left of the pivot, and all elements larger than the pivot are moved to the right. When this process ends, the pivot element is in its final position.
3. Recursive sorting: Recursively perform the above steps on the two subarrays to the left and right of the pivot, until each subarray contains only one element.

✨ Code Implementation

Here is the complete implementation of quick sort, using the first element as the pivot for the partition method:

1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// This function partitions a segment [a[left], a[right]] of array a according to the pivot value base
11int partition(int a[], int left, int right) {
12    int base = a[left]; // Choose the first element of the current segment as the pivot
13    while (left < right) {
14        // Scan from right to left to find the first element less than the pivot
15        while (left < right && a[right] >= base) {
16            right--;
17        }
18        a[left] = a[right]; // Move the element less than the pivot to the left
19
20        // Scan from left to right to find the first element greater than or equal to the pivot
21        while (left < right && a[left] < base) {
22            left++;
23        }
24        a[right] = a[left]; // Move the element greater than or equal to the pivot to the right
25    }
26    a[left] = base; // Place the pivot in its final position
27    return left; // Return the final index of the pivot
28}
29
30// Quick sort function that recursively sorts a segment of the array
31void quick_sort(int a[], int left, int right) {
32    if (left >= right) {
33        return; // If the current segment has length 1 or is empty, no sorting needed
34    }
35    int mid = partition(a, left, right); // Partition the current segment and get the pivot's index
36
37    quick_sort(a, left, mid - 1); // Recursively quick sort the left sub-segment
38    quick_sort(a, mid + 1, right); // Recursively quick sort the right sub-segment
39}
40
41int main() {
42        int n = 0;
43        cin >> n;
44        for (int i = 0; i < n; i++) {
45                cin >> a[i];
46        }
47        quick_sort(a, 0, n - 1);
48        for (int i = 0; i < n; i++) {
49                cout << a[i] << ' ';
50        }
51        cout << endl;
52        return 0;
53}

✨ Execution Example

Using the array [6, 3, 8, 1, 5, 2, 7, 4] as an example:

First round of partitioning: partition(a, 0, 7), choosing base = a[0] = 6

After partitioning: [4, 3, 2, 1, 5, 6, 7, 8], 6 is in its final position (index 5), everything on the left is <6, everything on the right is >=6.

Recursively sort the left half [4, 3, 2, 1, 5] (indices 0~4):

• base=4, after partitioning: [2, 3, 1, 4, 5]
• Recurse on [2, 3, 1]: base=2, after partitioning: [1, 2, 3]
• Recurse on [1]: base case, return
• Left half sorting complete: [1, 2, 3, 4, 5]

Recursively sort the right half [7, 8] (indices 6~7):

• base=7, after partitioning: [7, 8]
• Sorting complete

Final result: [1, 2, 3, 4, 5, 6, 7, 8]

✨ Algorithm Evaluation

Time Complexity

• Best case: O(n log n), when the partition operation splits the array into two nearly equal subarrays each time
• Average case: O(n log n), this is typical for randomly arranged arrays
• Worst case: O(n^2), when the array is nearly sorted or completely reversed, each partition only reduces one element

Space Complexity

The space complexity of quick sort depends on the depth of recursion, which can be optimized by recursing on the shorter subarray first:

• Best case: O(log n), balanced partitioning
• Worst case: O(n), unbalanced partitioning

Stability: Unstable sort. Equal elements may change their relative positions due to partitioning.

Advantages:

• Efficient: Very fast in most cases, especially superior to other O(n log n) algorithms like merge sort in terms of memory access patterns
• In-place sorting: Requires almost no extra space besides the stack space needed for recursion

Disadvantages:

• Unstable: Equal elements may change their relative positions due to partitioning
• Worst-case performance: Although uncommon, it performs poorly on nearly sorted arrays. This can be mitigated by randomly selecting the pivot

✨ Detailed Problem-Solving Steps

When using quick sort:

1. Choose the pivot element: The simplest approach is to pick the first or last element. To avoid worst-case scenarios, you can use the "median of three" method (taking the median of the first, middle, and last elements) or random selection.
2. Perform the partition operation: Place elements smaller than the pivot on the left and elements greater than or equal to the pivot on the right. After the partition operation, the pivot element is in its final correct position.
3. Recursively sort subarrays: Recursively apply quick sort to the subarrays on the left and right of the pivot.
4. Confirm the termination condition: When the subarray length is 0 or 1, return directly.

Quick Sort vs Merge Sort — how to choose:

• Need stable sorting → use merge sort
• Memory-constrained, want actual runtime speed → use quick sort
• Data is nearly sorted → merge sort is better (quick sort may degrade to O(n^2))
• In competitions, you generally just use the sort() function, whose underlying implementation is typically an optimized version of quick sort

✨ Common Mistakes

• Poor pivot choice leading to worst case: If the array is already sorted (ascending or descending) and the first element is always chosen as the pivot, the partition will be extremely unbalanced, degrading time complexity to O(n^2). The solution is to randomly select the pivot or use the median-of-three method.
• Missing left < right in the partition loop condition: The inner while loops must always maintain the left < right constraint, otherwise the pointers may cross and go out of bounds.
• Improper handling of equal elements: If the array contains many equal elements and all elements equal to base are placed on one side during partitioning, severe imbalance results. An improvement is "three-way partitioning": dividing the array into <base, =base, and >base sections.
• Forgetting to place base back in the correct position: The partition operation must place base at the position where left==right at the end; otherwise, subsequent recursions will miss this element.
• Array out of bounds: When calling quick_sort(a, left, mid-1), if mid=0 then mid-1=-1, so you need to ensure left >= right returns directly.

III. Homework

Programming Exercises

1. Patient Queue: L3122