Quick Sort Algorithm: Implementation and Analysis in C Language

Quick Sort is an efficient sorting algorithm that employs a divide-and-conquer strategy. Due to its excellent performance, Quick Sort is widely used in practical applications. This article will delve into the basic principles of Quick Sort, its implementation in C language, and its performance analysis.

1. Principles of Quick Sort Algorithm

The basic idea of Quick Sort is to select a “pivot” value and then partition the array to be sorted into two parts:

The left part contains all elements less than or equal to the pivot value.
The right part contains all elements greater than the pivot value.

Next, Quick Sort is recursively applied to these two parts. Ultimately, when all subarrays are sorted, the entire array is sorted as well.

1.1 Algorithm Steps

Select a pivot value from the array.
Partition the other elements into left and right sides based on the pivot value.
Recursively perform the same operation on the left and right sides.
Recursion continues until each subarray has a size of 0 or 1, at which point it is considered sorted.

1.2 Basic Example

Suppose we want to perform Quick Sort on the following array:

counter(line[10, 7, 8, 9, 1, 5]

After selecting 8 as the pivot value, the array is partitioned into:

counter(line[7, 1, 5] [8] [10,9]

Then, we repeat the above process on the segments [7,1,5] and [10,9], ultimately obtaining the sorted result [1,5,7,8,9,10].

2. C Language Implementation of Quick Sort

Below is a code example of the Quick Sort algorithm implemented in C language:

#include <stdio.h>
// Function declaration
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
// Main function
int main() {
    int arr[] = {10, 7, 8 ,9 ,1 ,5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    quickSort(arr ,0 ,n - 1);
    printf("\n\nSorted array: \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) {
       // Find the partition point, ensuring arr[pivot] is in the correct position
       int pivot_index = partition(arr ,low ,high);
       // Recursively call quickSort on the two sides of the partition
       quickSort(arr ,low,pivot_index - 1);
       quickSort(arr,pivot_index + 1, high);
   }
}
// Partition function to determine the position of the selected pivot and rearrange elements
int partition(int arr[],int low,int high) {
   // Pivot selection, here the rightmost element is chosen as the pivot
   int pivot_value = arr[high];
   int smaller_index = low - 1;
   for (int j = low; j <= high - 1; j++) {
     if (arr[j] <= pivot_value) {
         smaller_index++;
         // Swap the current number with the start of the smaller number range
         swap(&arr[smaller_index], &arr[j]);
     }
   }
   // Swap the pivot to its correct position
   swap(&arr[smaller_index + 1], &arr[high]);
   // Return the new partition index
   return smaller_index + 1;
}

Function Descriptions

quickSort: Executes the main Quick Sort logic, including termination condition checks and recursive calls.
partition: Performs the actual data rearrangement and returns the newly obtained partition index.

Error Handling and Testing

To ensure the code works correctly, we can run the above code and observe the output. Additionally, you can try using different datasets to verify whether the program can still correctly sort the data in ascending order. During debugging, it is important to pay attention to edge cases, such as empty inputs, single elements, and both nearly sorted and completely unsorted data, to evaluate performance under different conditions. These practices can help you enhance your problem-solving skills and practical techniques.

Performance Analysis

In the best case (for example, when the median is accurately chosen as the pivot), the average time complexity is O(n log n). However, in the worst case (such as when the input is nearly sorted and the basic substitution remains inefficient), the complexity can degrade to O(n²).

To mitigate the impact of such worst-case scenarios, measures can be taken, such as randomly selecting the pivot or using a three-way partitioning Quick Sort method. These approaches can ensure better performance and enhance overall efficiency.

Conclusion

This article introduced what Quick Sort is and how it works, along with a clear and simple implementation example in C language. Additionally, it discussed its time complexity characteristics and optimization suggestions. I hope this article helps you gain a deeper understanding of this classic algorithm! If you are interested in this content, feel free to explore more knowledge about advanced data structures and algorithms.