I. In-Class Exercises

Programming Exercises

1. Array Sort: 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 both 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 selection methods include random selection, choosing the first element, or 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 are moved to the right. After this process, 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

Below is the complete implementation of quick sort, using the first element as the pivot:

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]] based on the pivot value
11int partition(int a[], int left, int right) {
12    int base = a[left]; // Choose the first element as the pivot
13    while (left < right) {
14        // Scan from right to left, 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, 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, recursively sorts a segment of the array
31void quick_sort(int a[], int left, int right) {
32    if (left >= right) {
33        return; // If the segment has length 1 or is empty, no sorting needed
34    }
35    int mid = partition(a, left, right); // Partition the segment and get the pivot's index
36
37    quick_sort(a, left, mid - 1); // Recursively sort the left sub-segment
38    quick_sort(a, mid + 1, right); // Recursively 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 partition: partition(a, 0, 7), choosing base = a[0] = 6

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

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

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

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

• base=7, after partition: [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 splits the array into two nearly equal subarrays each time
• Average case: O(n log n), typical for randomly arranged arrays
• Worst case: O(n^2), when the array is nearly sorted or completely reversed, each partition reduces only one element

Space Complexity

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

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

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

Advantages:

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

Disadvantages:

• Unstable: Equal elements may change relative positions due to partitioning
• Worst-case performance: Although uncommon, performs poorly on nearly sorted arrays. Can be mitigated by random pivot selection

Detailed Problem-Solving Steps

When using quick sort:

1. Choose the pivot element: The simplest approach is to choose the first or last element. To avoid worst case, use the "median of three" method (take the median of the first, middle, and last elements) or random selection.
2. Execute the partition operation: Place elements smaller than the pivot on the left, elements greater than or equal to the pivot on the right. After partition, the pivot 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:

• Need stable sorting -> use merge sort
• Memory constrained, pursuing actual speed -> use quick sort
• Data is nearly sorted -> merge sort is better (quick sort may degrade to O(n^2))
• In competitions, generally use sort() directly, which is typically an optimized version of quick sort under the hood

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 pivot, the partition will be extremely unbalanced, degrading time complexity to O(n^2). The solution is random pivot selection or median of three.
• Missing left < right in partition loop conditions: The inner while loops must always maintain the left < right constraint, otherwise pointers may cross and go out of bounds.
• Improper handling of equal elements: If the array has many equal elements and all elements equal to base are placed on one side, it causes severe imbalance. An improvement is "three-way partitioning": dividing the array into <base, =base, >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 recursion will miss this element.
• Array out of bounds: When calling quick_sort(a, left, mid-1), if mid=0 then mid-1=-1. Make sure to return directly when left >= right.

III. Homework

Programming Exercises

1. Patient Queue: L3122