Sorting Algorithms: Quick Sort in C

What You’ll Learn 📚

• Understand the core concepts of Quick Sort
• Learn key terminology with friendly definitions
• Explore simple to complex examples
• Get answers to common questions
• Troubleshoot common issues

Introduction to Quick Sort

Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer approach. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Key Terminology

• Pivot: An element selected from the array to partition the data.
• Partitioning: The process of rearranging the array so that elements less than the pivot are on the left, and those greater are on the right.
• Recursive: A function that calls itself to solve smaller instances of the same problem.

Simple Example

#include <stdio.h>

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];  // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;    // increment index of smaller element
            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");
}

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

Sorted array: 
1 5 7 8 9 10 

Progressively Complex Examples

Example 1: Handling Larger Arrays

Try modifying the array to include more elements and see how Quick Sort handles larger datasets.

Example 2: Different Pivot Selection

Experiment with different pivot selection strategies, such as picking the first element or a random element.

Example 3: Visualizing the Process

Use a debugger or print statements to visualize how the array changes with each recursive call.

Common Questions and Answers

1. What is the time complexity of Quick Sort?

   In the average case, Quick Sort has a time complexity of O(n log n). In the worst case, it's O(n^2), but this is rare with good pivot selection.

2. Why is Quick Sort preferred over other sorting algorithms?

   Quick Sort is often faster in practice due to its efficient cache performance and average-case complexity.

3. Can Quick Sort be implemented iteratively?

   Yes, though it is more complex. Recursive implementations are more straightforward and commonly used.

Troubleshooting Common Issues

Ensure your pivot selection and partitioning logic are correct to avoid infinite recursion or incorrect sorting.

If your array isn't sorting correctly, try printing the array at each step to debug the partitioning process.

Practice Exercises

• Implement Quick Sort with a different pivot selection strategy.
• Modify the code to sort in descending order.
• Use Quick Sort to sort an array of strings.

Keep practicing, and soon you'll master Quick Sort! 🚀