Detailed Explanation of Quick Sort Implementation in C

Quick Sort is an efficient sorting algorithm that is also based on the “divide and conquer” principle. Its core idea is to select a “pivot value” to partition the array into two parts: one part contains elements less than the pivot value, and the other part contains elements greater than the pivot value, followed by recursively sorting both parts.Core Idea：

• Select a pivot value (pi)
• Partition the array: place elements less than the pivot value on the left, and elements greater than the pivot value on the right
• Recursively perform the same operation on the left and right subarrays

Code ImplementationHeader File

#include <stdio.h>

Main Function

int main() {    int arr[] = { 10, 7, 8, 9, 1, 5 };    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");    printArray(arr, n);
    return 0;}

Function to Swap Two Integers

// Function to swap the values of two integers
void swap(int* a, int* b) {    int t = *a;    *a = *b;    *b = t;}

Main Function of Quick Sort

// Main function of Quick Sort
// arr: array to be sorted
// low: starting index
// high: ending index
void quickSort(int arr[], int low, int high) {    if (low < high)     {        // pi is the index of the pivot value, after partitioning arr[pi] is in the correct position        int pi = partition(arr, low, high);
        // Recursively sort the left subarray of the pivot value        quickSort(arr, low, pi - 1);        // Recursively sort the right subarray of the pivot value        quickSort(arr, pi + 1, high);    }}

Partition Operation: Select a pivot value and divide the array into two parts

// Partition operation: select a pivot value and divide the array into two parts
// Return the final index of the pivot value
int partition(int arr[], int low, int high) {    // Choose the rightmost element as the pivot value    int pivot = arr[high];      // Boundary index for the area less than the pivot value    int i = (low - 1);      
    for (int j = low; j <= high - 1; j++)     {        // If the current element is less than or equal to the pivot value        if (arr[j] <= pivot)         {            // Expand the area less than the pivot value            // i starts incrementing from low            i++;  
            // Place the current element in that area            swap(&arr[i], &arr[j]);          }    }    // Place the pivot value in the correct position (between the less than and greater than areas)    swap(&arr[i + 1], &arr[high]);    return (i + 1);  // Return the index of the pivot value}

Print Array

// Function to print the array
void printArray(int arr[], int size) {    for (int i = 0; i < size; i++)        printf("%d ", arr[i]);    printf("\n");}

Analysis of the quickSort Function：

• Function: Recursively implements quick sort
• Implementation Steps:

1. Perform partition operation on the array to get the pivot value index<span>pi</span>
2. Recursively sort the left subarray of the pivot value (<span>low</span> to <span>pi-1</span>)
3. Recursively sort the right subarray of the pivot value (<span>pi+1</span> to <span>high</span>)

Analysis of the partition Function：

• Function: Implements the partition operation and returns the final position of the pivot value
• Implementation Steps:

1. Select the rightmost element as the pivot value
2. Maintain a boundary index for the area less than the pivot value<span>i</span>
3. Traverse the array and swap elements less than or equal to the pivot value to the left area
4. Place the pivot value to the right of the left area, forming two partitions

Characteristics of Quick Sort

• Advantages
• Average time complexity isO(n log n), usually faster than merge sort in practical applications
• In-place sorting (requires only O(log n) of recursive stack space)
• Cache-friendly with good locality
• Disadvantages
• Worst-case time complexity isO(n²) (when the array is sorted and the two end elements are chosen as pivots)
• Unstable sorting algorithm (the relative position of equal elements may change)

Optimization Techniques

1. Pivot Value Selection：

• Randomly select the pivot value
• Median of three method (median of the first, last, and middle elements)

Optimization for Small Subarrays：

• When the subarray size is small (e.g., less than 10 elements), use insertion sort instead

Tail Recursion Optimization：

• Use loops for larger subarrays and recursion for smaller subarrays to reduce stack space usage

Applicable Scenarios

• Sorting large-scale data
• Scenarios with high average performance requirements
• Memory-constrained environments (due to in-place sorting characteristics)

Many standard library sorting functions in programming languages use quick sort or its variants (e.g., C++’s<span>std::sort</span>).