C++ Program To Implement Qsort Using Function Pointers

Generic sorting is a fundamental task in programming, but handling various data types and custom comparison logic can be challenging. A flexible sorting mechanism is crucial for efficient code.

In this article, you will learn how to implement a generic sorting function similar to C's qsort in C++ using function pointers, enabling it to sort different data types based on custom comparison rules.

Problem Statement

Standard sorting algorithms often operate on specific data types (e.g., std::sort with int, double, etc.) or require custom comparison objects (functors or lambdas) for complex types. When working with C-style arrays or needing a C-compatible interface, creating a single, generic sorting function that can handle arbitrary data types and custom comparison criteria using only function pointers becomes a necessity. This avoids rewriting the entire sorting logic for each new data type or comparison rule.

Example

Consider an array of integers [5, 2, 8, 1, 9]. A generic qsort-like function should be able to sort this into [1, 2, 5, 8, 9]. If we then have an array of strings, the same sorting function, provided with a different comparison logic, should sort them alphabetically.

Background & Knowledge Prerequisites

To understand this article, readers should be familiar with:

• C++ Basics: Fundamental data types, arrays, loops, and functions.
• Pointers: Understanding void* (generic pointers), pointer arithmetic, and type casting.
• Function Pointers: Declaring, assigning, and calling functions through pointers.
• Memory Management: Concepts of sizeof operator.

Use Cases or Case Studies

Function pointers in qsort-like implementations are powerful for various scenarios:

• Sorting Primitive Arrays: Sorting arrays of int, float, double, etc., in ascending or descending order using a single generic sort function.
• Sorting String Arrays: Custom comparison for strings (e.g., case-sensitive, case-insensitive, or by length).
• Sorting Custom Structs/Objects: Arranging arrays of complex data structures based on one or more of their member fields (e.g., sorting Student objects by ID, then by name, or age).
• Sorting with Different Criteria: Providing dynamic comparison logic at runtime without recompiling the sorting function. For instance, a user might choose to sort a list of products by price, then by name, then by category.
• Interfacing with C Libraries: When a C++ program needs to interact with a C library that expects a qsort-compatible comparison function.

Solution Approaches

We will implement a my_qsort function that mimics the standard C qsort signature, using function pointers for comparison.

Approach 1: Implementing my_qsort for Integers

This approach demonstrates the core my_qsort logic and how to write a comparison function for integers.

Summary: Implement a basic quick sort algorithm that accepts a generic base pointer, number of elements, size of each element, and a comparison function pointer, then define an integer comparison function for it.

// Custom qsort for Integers
#include <iostream>
#include <cstring> // For memcpy in a real qsort, but not strictly needed for this basic example

// Function pointer type for comparison
typedef int (*CompareFunc)(const void*, const void*);

// Helper function to swap two elements
void swap(void* a, void* b, size_t size) {
    // Create a temporary buffer on the stack
    // This is safe for small 'size'. For very large sizes,
    // a dynamically allocated buffer or a different swap strategy might be better.
    char temp[size];
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
}

// Partition function for Quick Sort
int partition(void* base, size_t num, size_t size, CompareFunc compar) {
    // Treat base as a char array to perform byte-level pointer arithmetic
    char* arr = static_cast<char*>(base);
    void* pivot = arr + (num - 1) * size; // Last element as pivot

    int i = -1; // Index of smaller element

    for (int j = 0; j < num - 1; ++j) {
        // Compare current element (arr + j*size) with pivot
        if (compar(arr + j * size, pivot) <= 0) {
            i++;
            swap(arr + i * size, arr + j * size, size);
        }
    }
    swap(arr + (i + 1) * size, pivot, size);
    return (i + 1);
}

// Recursive Quick Sort implementation
void my_qsort_recursive(void* base, size_t num, size_t size, CompareFunc compar) {
    if (num < 2) {
        return;
    }

    int pi = partition(base, num, size, compar);

    // Recursively sort elements before partition and after partition
    my_qsort_recursive(base, pi, size, compar);
    my_qsort_recursive(static_cast<char*>(base) + (pi + 1) * size, num - pi - 1, size, compar);
}

// Main qsort function wrapper
void my_qsort(void* base, size_t num, size_t size, CompareFunc compar) {
    my_qsort_recursive(base, num, size, compar);
}

// Comparison function for integers (ascending order)
int compareInts(const void* a, const void* b) {
    int valA = *static_cast<const int*>(a);
    int valB = *static_cast<const int*>(b);
    if (valA < valB) return -1;
    if (valA > valB) return 1;
    return 0;
}

int main() {
    // Step 1: Initialize an array of integers
    int arr[] = {5, 2, 8, 1, 9, 3};
    size_t n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (size_t i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Step 2: Sort the array using my_qsort with compareInts
    my_qsort(arr, n, sizeof(int), compareInts);

    cout << "Sorted array (ascending): ";
    for (size_t i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Run

Sample Output:

Original array: 5 2 8 1 9 3 
Sorted array (ascending): 1 2 3 5 8 9

Stepwise Explanation:

1. CompareFunc Typedef: We define CompareFunc as a type alias for a function pointer that takes two const void* arguments and returns an int. This is the standard signature for qsort comparison functions.
2. swap Function: This helper function takes two void* pointers (a, b) and the size of the elements. It uses memcpy to correctly swap the byte content of the two elements, regardless of their actual type.
3. partition Function: This is a core part of the Quick Sort algorithm.

• It takes the base pointer, number of elements, element size, and the compar function.
• It casts the void* base to char* to perform byte-level pointer arithmetic (arr + j * size) to access individual elements correctly.
• It uses the compar function to determine the relative order of elements compared to the pivot.
• It rearranges elements such that elements smaller than or equal to the pivot come before it, and larger elements come after.

1. my_qsort_recursive Function: This implements the recursive quicksort logic.

• It handles the base case (num < 2).
• It calls partition to get the pivot index.
• It then recursively calls itself for the sub-arrays before and after the pivot. Note the careful pointer arithmetic to pass the correct base address for the right sub-array (static_cast(base) + (pi + 1) * size).

1. my_qsort Function: A simple wrapper that initiates the recursive quicksort.
2. compareInts Function: This is a concrete implementation of CompareFunc for integers.

• It takes const void* a and const void* b.
• Inside, it static_casts these generic pointers to const int* to dereference them and access their integer values.
• It returns -1 if a is less than b, 1 if a is greater than b, and 0 if they are equal, adhering to the qsort comparison contract.

1. main Function:

• An integer array arr is declared.
• my_qsort is called, passing the array, its size, the size of each element (sizeof(int)), and the compareInts function pointer. This demonstrates how the generic my_qsort uses the specific compareInts logic.

Approach 2: Using my_qsort for Custom Structs

This approach extends my_qsort to sort an array of custom data structures by specific fields.

Summary: Define a Person struct and create a comparison function that sorts Person objects by their age using the my_qsort function developed previously.

// Custom qsort for Custom Structs
#include <iostream>
#include <string>
#include <vector> // Using vector just for easier printing, but data is C-style array
#include <cstring> // For memcpy

// Function pointer type for comparison (re-using from Approach 1)
typedef int (*CompareFunc)(const void*, const void*);

// Helper function to swap two elements (re-using from Approach 1)
void swap(void* a, void* b, size_t size) {
    char temp[size];
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
}

// Partition function for Quick Sort (re-using from Approach 1)
int partition(void* base, size_t num, size_t size, CompareFunc compar) {
    char* arr = static_cast<char*>(base);
    void* pivot = arr + (num - 1) * size; 

    int i = -1;

    for (int j = 0; j < num - 1; ++j) {
        if (compar(arr + j * size, pivot) <= 0) {
            i++;
            swap(arr + i * size, arr + j * size, size);
        }
    }
    swap(arr + (i + 1) * size, pivot, size);
    return (i + 1);
}

// Recursive Quick Sort implementation (re-using from Approach 1)
void my_qsort_recursive(void* base, size_t num, size_t size, CompareFunc compar) {
    if (num < 2) {
        return;
    }

    int pi = partition(base, num, size, compar);

    my_qsort_recursive(base, pi, size, compar);
    my_qsort_recursive(static_cast<char*>(base) + (pi + 1) * size, num - pi - 1, size, compar);
}

// Main qsort function wrapper (re-using from Approach 1)
void my_qsort(void* base, size_t num, size_t size, CompareFunc compar) {
    my_qsort_recursive(base, num, size, compar);
}

// Custom struct
struct Person {
    std::string name;
    int age;
};

// Comparison function for Person structs (sort by age, ascending)
int comparePeopleByAge(const void* a, const void* b) {
    const Person* personA = static_cast<const Person*>(a);
    const Person* personB = static_cast<const Person*>(b);
    if (personA->age < personB->age) return -1;
    if (personA->age > personB->age) return 1;
    return 0;
}

// Comparison function for Person structs (sort by name, ascending)
int comparePeopleByName(const void* a, const void* b) {
    const Person* personA = static_cast<const Person*>(a);
    const Person* personB = static_cast<const Person*>(b);
    return personA->name.compare(personB->name);
}


int main() {
    // Step 1: Initialize an array of Person structs
    Person people[] = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 25},
        {"Eve", 28}
    };
    size_t n = sizeof(people) / sizeof(people[0]);

    cout << "Original people list:" << endl;
    for (size_t i = 0; i < n; ++i) {
        cout << "Name: " << people[i].name << ", Age: " << people[i].age << endl;
    }
    cout << endl;

    // Step 2: Sort the array by age using my_qsort with comparePeopleByAge
    my_qsort(people, n, sizeof(Person), comparePeopleByAge);

    cout << "Sorted by age (ascending):" << endl;
    for (size_t i = 0; i < n; ++i) {
        cout << "Name: " << people[i].name << ", Age: " << people[i].age << endl;
    }
    cout << endl;

    // Step 3: Sort the array by name using my_qsort with comparePeopleByName
    my_qsort(people, n, sizeof(Person), comparePeopleByName);

    cout << "Sorted by name (ascending):" << endl;
    for (size_t i = 0; i < n; ++i) {
        cout << "Name: " << people[i].name << ", Age: " << people[i].age << endl;
    }
    cout << endl;

    return 0;
}

Run

Sample Output:

Original people list:
Name: Alice, Age: 30
Name: Bob, Age: 25
Name: Charlie, Age: 35
Name: David, Age: 25
Name: Eve, Age: 28

Sorted by age (ascending):
Name: Bob, Age: 25
Name: David, Age: 25
Name: Eve, Age: 28
Name: Alice, Age: 30
Name: Charlie, Age: 35

Sorted by name (ascending):
Name: Alice, Age: 30
Name: Bob, Age: 25
Name: Charlie, Age: 35
Name: David, Age: 25
Name: Eve, Age: 28

Stepwise Explanation:

1. Person Struct: A simple Person struct is defined with name (a std::string) and age (an int).
2. my_qsort Implementation (Reused): The my_qsort and its helper functions (swap, partition, my_qsort_recursive) from Approach 1 are reused without modification. This highlights the genericity of the sorting algorithm itself.
3. comparePeopleByAge Function:

• This comparison function takes two const void* pointers.
• It casts them to const Person* to access the age member of the Person objects.
• It then compares their ages and returns -1, 0, or 1 based on the comparison, sorting by age in ascending order.

1. comparePeopleByName Function:

• Similar to comparePeopleByAge, this function casts the void* pointers to const Person*.
• It then uses std::string::compare to sort Person objects alphabetically by their name member.

1. main Function:

• An array of Person structs is initialized.
• The initial list is printed.
• my_qsort is called twice:
• First, with comparePeopleByAge to sort the array by age.
• Second, with comparePeopleByName to sort the array by name. This demonstrates the dynamic behavior: the same my_qsort function can sort the same data in different ways by simply providing a different comparison function.

Conclusion

Implementing qsort using function pointers in C++ provides a robust and generic way to sort C-style arrays of any data type based on custom comparison logic. By abstracting the comparison operation through a function pointer, the core sorting algorithm remains decoupled from the specific data type and ordering criteria. This flexibility is invaluable for building generic libraries, handling diverse data, and interacting with C-style interfaces.

Summary

• Generic Sorting: Function pointers enable a single sorting algorithm to work with various data types.
• void* Pointers: Used for generic memory addressing in my_qsort parameters.
• size_t size: Crucial for correct pointer arithmetic when accessing elements in void* arrays.
• Comparison Function Signature: int (*compar)(const void*, const void*) is standard; it returns -1, 0, or 1 based on relative order.
• Type Casting: Inside the comparison function, void* pointers must be cast to the actual data type pointers (e.g., int*, Person*) to access their values or members.
• Flexibility: Provides runtime configurability for sorting criteria, allowing the same data to be sorted in multiple ways without changing the core sort logic.