Principles and Practice of Quick Sort Algorithm in C Language

Quick sort is a highly efficient sorting algorithm widely used in various programming fields. It employs a divide-and-conquer approach, with an average time complexity of O(n log n). Let us explore the principles of quick sort and its implementation in C language.

Basic Idea of Quick Sort

The core idea of quick sort is to partition an array into two parts and then recursively sort these two parts. The specific steps are as follows:

1. Select a Pivot: Choose an element from the array as the pivot, typically the first element, the last element, or a randomly selected element.
2. Partition Operation: Rearrange the array so that all elements smaller than the pivot are on its left, and all elements greater than the pivot are on its right. At this point, the pivot is in its final position.
3. Recursive Processing: Continue the above process on the left and right subarrays.

Detailed Steps of the Algorithm

1. Select a Pivot

Common methods include:

• Fixed selection, i.e., choosing the first or last element.
• Random selection to avoid the worst-case scenario.

2. Partition Process

The main goal is to rearrange the array such that:

• All elements less than or equal to the pivot move to the left of the pivot.
• All elements greater than the pivot move to its right.

3. Recursive Calls

Repeat the above process for the left and right subarrays until each subarray contains zero or one element, making them sorted.

Code Example of Quick Sort in C Language

Below is a piece of code implementing the quick sort algorithm in C language:

#include <stdio.h>
// Function declaration
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);

int main() {
    // Test example
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    quickSort(arr, 0, n - 1);
    printf("\n\nAfter sorting:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

// Quick sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Get partition index, arr[p] is in the correct position
        int pi = partition(arr, low, high);

        // Recursively call quick sort on the left and right subarrays
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Partition function, implements the swapping logic described above
int partition(int arr[], int low, int high) {
    // Set the last number as pivot
    int pivot = arr[high];
    // Initialize the smaller index pointer
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++; // If current value ≤ pivot, swap positions
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Place pivot in the correct position and return the new pivot index
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

Program Analysis

The program first includes the standard input-output header file<span><stdio.h></span>. It then defines the <span>quickSort</span> and <span>partition</span> functions. In the <span>main</span> function, we define the array to be sorted and record its length, then call <span>quickSort</span> to process the array.

<span>quickSort</span> Function:

• Takes three parameters: the array to be sorted, the starting index, and the ending index.
• First checks if the starting index is less than the ending index; if so, it proceeds to the next step; if not, it indicates that this range has already been processed and does not need further recursion.
• Uses <span>partition</span> to find the correct position and returns it, then recursively applies quick sort to the left and right intervals.

<span>partition</span> Function:

• Takes the array to be sorted and its current low and high indices, reorganizing the data within this range according to the pivot;
• Finally returns the index of the pivot in the new order.

Through this series of operations, this code can efficiently complete the overall scheduling of the data set, achieving a fast auxiliary sorting function.

Conclusion

This article provides a detailed introduction to the important techniques that must be followed in the quick sort strategy in C language. This classification is precise, simple, and efficient, making it an essential part of writing large applications and system use case printing. After mastering the dynamic feedback mechanism, one can also customize the style of content display as needed to enhance readability. This is also one of the necessary conditions for engineers in today’s software development industry to further promote the advancement of knowledge-based technology.