C Program For Quick Sort Using Recursion

Sorting data efficiently is fundamental in computer science, enabling faster searching and better organization. In this article, you will learn how to implement the Quick Sort algorithm using recursion in C, a powerful technique for organizing arrays.

Problem Statement

The challenge of arranging elements in an array into a specific order, such as ascending or descending, is a frequent task in programming. For large datasets, inefficient sorting algorithms can lead to significant performance bottlenecks, making the choice of an optimal sorting algorithm critical for application responsiveness and resource utilization.

Example

Consider an unsorted array of integers. After applying Quick Sort, the elements will be arranged in ascending order.

Input Array: [10, 7, 8, 9, 1, 5]

Output Array after Quick Sort: [1, 5, 7, 8, 9, 10]

Background & Knowledge Prerequisites

To understand Quick Sort using recursion in C, readers should be familiar with the following:

• C Language Basics: Variables, data types, loops (for, while), conditional statements (if-else).
• Arrays: Declaring, initializing, and accessing elements in one-dimensional arrays.
• Functions: Defining and calling functions, passing arguments, and returning values.
• Pointers: Basic understanding of pointers, especially when used with arrays to modify values directly.
• Recursion: The concept of a function calling itself, including base cases and recursive steps.

Use Cases or Case Studies

Quick Sort is widely used across various domains due to its efficiency in practice. Here are a few practical applications:

• Database Management Systems: Used internally to sort records based on specific keys, optimizing query performance.
• Search Algorithms: Pre-sorting data enables the use of highly efficient search algorithms like binary search.
• Data Analysis and Visualization: Arranging data points helps in identifying trends, outliers, and preparing data for graphical representation.
• Operating System Scheduling: Processes can be sorted by priority or arrival time to manage their execution efficiently.
• In-memory Sorting: Excellent choice for sorting large arrays that fit into memory, often outperforming other algorithms like Merge Sort in terms of constant factors.

Solution Approaches

Quick Sort is a "divide and conquer" algorithm. 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.

Standard Recursive Quick Sort

This approach involves two main functions: a partition function to arrange elements around a pivot, and a quickSort function that recursively calls itself on the sub-arrays.

// Quick Sort using Recursion
#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

/*
 * This function takes the last element as pivot, places
 * the pivot element at its correct position in sorted
 * array, and places all smaller (than pivot) to left
 * of pivot and all greater elements to right of pivot.
 */
int partition(int arr[], int low, int high) {
    // Step 1: Choose the pivot (last element in this implementation)
    int pivot = arr[high];
    // Index of smaller element and indicates the right position of the pivot found so far
    int i = (low - 1);

    // Step 2: Iterate through the array from low to high-1
    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++; // Increment index of smaller element
            swap(&arr[i], &arr[j]); // Swap current element with element at i
        }
    }
    // Step 3: Place the pivot element at its correct sorted position
    swap(&arr[i + 1], &arr[high]);
    return (i + 1); // Return the partitioning index
}

/*
 * The main function that implements QuickSort
 * arr[] --> Array to be sorted,
 * low   --> Starting index,
 * high  --> Ending index
 */
void quickSort(int arr[], int low, int high) {
    // Step 1: Base case for recursion
    if (low < high) {
        // Step 2: pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Step 3: Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);  // Sort left sub-array
        quickSort(arr, pi + 1, high); // Sort right sub-array
    }
}

// Function to print an array
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]);

    printf("Original array: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

Original array: 10 7 8 9 1 5 
Sorted array: 1 5 7 8 9 10

Stepwise Explanation:

1. swap(int* a, int* b) Function: A utility function used to exchange the values of two integer pointers. This is crucial for rearranging elements within the array.
2. partition(int arr[], int low, int high) Function:

• It selects the last element of the sub-array (arr[high]) as the pivot.
• It initializes i (index of smaller element) to low - 1.
• It iterates from j = low to high - 1. If arr[j] is less than the pivot, i is incremented, and arr[i] and arr[j] are swapped. This places smaller elements to the left of i.
• Finally, the pivot (originally at arr[high]) is swapped with arr[i + 1], placing it in its correct sorted position.
• The function returns the index of the pivot (i + 1).

1. quickSort(int arr[], int low, int high) Function:

• This is the recursive function. Its base case is if (low < high), meaning if there's more than one element in the sub-array to sort.
• It calls partition to get the pi (partitioning index), where the pivot is now correctly placed.
• It then makes two recursive calls:
• quickSort(arr, low, pi - 1): Sorts the sub-array to the left of the pivot.
• quickSort(arr, pi + 1, high): Sorts the sub-array to the right of the pivot.
• These recursive calls continue until the base case is met (sub-arrays of one or zero elements), at which point the entire array is sorted.

1. printArray(int arr[], int size) Function: A simple utility function to display the contents of the array.
2. main() Function:

• Declares an unsorted integer array.
• Calculates its size.
• Prints the original array.
• Calls quickSort with the array, starting index (0), and ending index (n - 1).
• Prints the sorted array.

Conclusion

Quick Sort is a highly efficient, comparison-based sorting algorithm, particularly well-suited for large datasets due to its average-case time complexity of O(n log n). Its recursive nature, breaking down a large problem into smaller, manageable sub-problems, exemplifies the "divide and conquer" paradigm. While its worst-case performance can degrade to O(n^2), this is rare in practice and often mitigated by choosing an effective pivot strategy.

Summary

• Quick Sort is a "divide and conquer" sorting algorithm.
• It works by selecting a pivot element and partitioning the array around it.
• The partition function places elements smaller than the pivot to its left and larger elements to its right.
• The quickSort function recursively applies this process to the sub-arrays.
• It offers an average-case time complexity of O(n log n), making it very efficient for most real-world scenarios.
• Implementation in C requires understanding of functions, pointers, and recursive calls.