3. Quick Sort Function

This is the recursive function that orchestrates the sorting process. It calls partition and then recursively calls itself for the sub-arrays.

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

4. Helper: Print Array Function

Useful for displaying the array before and after sorting.

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

5. Main Function (Putting it all together)

A demonstration of how to use Quick Sort.

#include <stdio.h> // For printf

// Function prototypes
void swap(int* a, int* b);
int partition(int arr[], int low, int high);
void quickSort(int arr[], int low, int high);
void printArray(int arr[], int size);

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);

    int arr2[] = {55, 23, 100, 4, 16, 42, 80, 1, 77};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    printf("\nOriginal array 2: ");
    printArray(arr2, n2);

    quickSort(arr2, 0, n2 - 1);

    printf("Sorted array 2: ");
    printArray(arr2, n2);

    return 0;
}

// Function definitions (as provided above)
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

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

Time and Space Complexity Analysis

Understanding the performance characteristics is crucial for choosing the right algorithm.

Time Complexity

• Best Case: O(N log N)

  Occurs when the pivot element always divides the array into two nearly equal halves. Each partitioning step takes O(N) time, and there are approximately log N levels of recursion (like a balanced binary tree). This is highly efficient for large datasets.

• Average Case: O(N log N)

  Even with random pivot choices, Quick Sort typically performs very well, achieving O(N log N) on average. The constant factors are generally smaller than other O(N log N) algorithms like Merge Sort.

• Worst Case: O(N²)

  This happens when the pivot selection consistently results in highly unbalanced partitions (e.g., always picking the smallest or largest element as the pivot). If the array is already sorted or reverse-sorted, and you always pick the first or last element as the pivot (as in our Lomuto implementation), one sub-array will always be empty, leading to N levels of recursion, with each level doing O(N) work. This makes it perform like Bubble Sort or Selection Sort.

  Techniques like "median-of-three" pivot selection or choosing a random pivot can significantly reduce the probability of hitting the worst-case scenario in practice.

Space Complexity

• Average Case: O(log N)

  This is due to the recursion stack. In a balanced partitioning scenario, the depth of the recursion tree is log N.

• Worst Case: O(N)

  If the partitioning is highly unbalanced (as in the worst-case time complexity), the recursion depth can go up to N, leading to O(N) space complexity for the call stack.

Advantages and Disadvantages of Quick Sort

Advantages

• Highly Efficient: Generally performs better than other O(N log N) algorithms like Merge Sort in practice, due to better cache performance and smaller constant factors.
• In-place Sorting: It requires minimal additional space (O(log N) average case for recursion stack), making it memory efficient.
• Parallelization: It's a natural candidate for parallel processing as the sub-problems are independent.

Disadvantages

• Worst-Case Performance: The O(N²) worst-case time complexity can be a significant concern, although it's rare with good pivot selection strategies.
• Not Stable: Quick Sort is not a stable sorting algorithm, meaning the relative order of equal elements is not preserved.
• Recursive Overhead: The recursive nature can lead to stack overflow issues for extremely large datasets or in environments with limited stack space, though iterative versions exist.

When to Use Quick Sort

Quick Sort is an excellent general-purpose sorting algorithm and is often the default choice in many standard libraries (e.g., C's qsort uses a Quick Sort variant). It's particularly well-suited for:

• Sorting large arrays where speed is a primary concern.
• Scenarios where in-place sorting is beneficial due to memory constraints.
• When stability is not a requirement.

Conclusion

Quick Sort is a powerful and efficient sorting algorithm that every C programmer should understand. Its elegant divide-and-conquer approach, coupled with its excellent average-case performance, makes it a cornerstone of efficient data processing. While being aware of its worst-case scenario is important, proper pivot selection techniques largely mitigate this risk in practical applications.

Experiment with the code examples provided, try different input arrays, and perhaps even implement a random pivot selection strategy to deepen your understanding. Happy coding!