Quick Sort is an efficient sorting algorithm based on the divide-and-conquer principle, with an average time complexity of O(n log n). It is very popular in practical applications. Its core idea is to select a pivot element, partition the array into two parts (elements less than the pivot on the left and elements greater than the pivot on the right), and then recursively sort these two parts.

I. Core Ideas of Quick Sort¶

1. Divide and Conquer: Decompose a large problem into smaller subproblems to solve.
2. Pivot Selection: Choose an element in the array as the pivot.
3. Partitioning: 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.
4. Recursive Sorting: Recursively sort the left and right subarrays.

II. Partitioning Process (Lomuto Partition Scheme)¶

Using the rightmost element of the array as the pivot. The specific steps are:
1. Initialize a pointer i pointing to the end of the “less than pivot” region (initially left-1).
2. Traverse the array from left to right-1. If the current element is less than the pivot, increment i and swap the current element into the “less than pivot” region.
3. After the traversal, swap the pivot element with the element at position i+1. At this point, the pivot element is in its final position.

III. C++ Code Implementation¶

1. Partition Function¶

// Partition function: returns the final position of the pivot element
int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];  // Select the rightmost element as the pivot
    int i = left - 1;         // Boundary of the "less than pivot" region (initially empty)
    for (int j = left; j < right; j++) {  // Traverse all elements except the pivot
        if (nums[j] < pivot) {            // Current element is less than the pivot
            i++;                          // Expand the "less than pivot" region
            swap(nums[i], nums[j]);       // Swap to the "less than pivot" region
        }
    }
    swap(nums[i + 1], nums[right]);       // Place the pivot in its final position
    return i + 1;                         // Return the pivot position
}

2. Quick Sort Main Function¶

// Quick sort main function: recursively sort the [left, right] interval of the array
void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;  // Base case: subarray length is 1 or 0, no need to sort

    int pivotIndex = partition(nums, left, right);  // Get the pivot position
    quickSort(nums, left, pivotIndex - 1);          // Recursively sort the left half
    quickSort(nums, pivotIndex + 1, right);         // Recursively sort the right half
}

3. Test Code¶

#include <iostream>
#include <vector>
using namespace std;

// Partition function
int partition(vector<int>& nums, int left, int right) { /* Same as above */ }

// Quick sort main function
void quickSort(vector<int>& nums, int left, int right) { /* Same as above */ }

int main() {
    vector<int> arr = {6, 3, 8, 5, 2, 7, 1, 4};
    int n = arr.size();

    cout << "Array before sorting: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    quickSort(arr, 0, n - 1);  // Call quick sort

    cout << "Array after sorting: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

IV. Execution Result¶

Array before sorting: 6 3 8 5 2 7 1 4 
Array after sorting: 1 2 3 4 5 6 7 8 

V. Key Explanations¶

1. In-place Sorting: The partitioning operation is performed on the original array without additional space.
2. Recursion Termination: The recursion stops when the subarray length is less than or equal to 1 (left >= right).
3. Time Complexity: Average O(n log n), worst case O(n²) (e.g., when the array is already sorted and the leftmost/rightmost element is chosen as the pivot). This can be optimized by randomly selecting the pivot.

Quick Sort is a frequently examined algorithm in interviews and real-world development. Mastering its partitioning logic and recursive thinking is key to understanding efficient sorting. Through the provided code and comments, beginners can gradually grasp its implementation principles.