C Program To Implement Qsort Using Function Pointers

In C programming, sorting arrays is a common task, but the type of data and the desired sorting order can vary greatly. In this article, you will learn how to leverage qsort from the standard library with function pointers to implement flexible and generic sorting solutions for various data types.

Problem Statement

When working with arrays in C, developers often face the challenge of sorting different data types (like integers, strings, or custom structures) in various orders (ascending, descending, or based on specific criteria). While a simple loop can sort a small array of integers, a generic solution is needed for larger, more complex scenarios. The qsort function from the C standard library provides a powerful, generalized sorting mechanism, but it requires a custom comparison logic that must be passed as a function pointer. Without understanding function pointers, utilizing qsort effectively for diverse data types becomes a significant hurdle, limiting code reusability and flexibility.

Example

Consider a scenario where you have an array of integers and need to sort them. A simple qsort call might look like this:

// Basic qsort for integers
#include <stdio.h>
#include <stdlib.h> // For qsort

// Comparison function for integers (ascending)
int compareIntegers(const void *a, const void *b) {
    int int_a = *(const int *)a;
    int int_b = *(const int *)b;
    return int_a - int_b;
}

int main() {
    int arr[] = {5, 2, 8, 1, 9, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    // Sort the array using qsort and the custom comparison function
    qsort(arr, n, sizeof(int), compareIntegers);

    printf("Sorted array (ascending): ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    return 0;
}

Run

Output:

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

This example shows qsort successfully sorting an integer array. The key element enabling this flexibility is the compareIntegers function, passed as a function pointer to qsort.

Background & Knowledge Prerequisites

To effectively use qsort with function pointers, it's beneficial to have a foundational understanding of:

• C Language Basics: Variables, data types, arrays, and functions.
• Pointers in C: How pointers work, dereferencing, and pointer arithmetic.
• void* Pointers: Understanding void* as a generic pointer type that can point to any data type and the necessity of type casting when dereferencing.
• Function Pointers: The concept of pointers that store the address of a function, allowing functions to be passed as arguments to other functions.
• Standard Library Functions: Familiarity with common functions from and .

Use Cases or Case Studies

Function pointers with qsort are invaluable for:

• Generic Sorting of Primitive Types: Sorting arrays of integers, floats, or characters in ascending or descending order.
• Alphabetical String Sorting: Arranging an array of C-style strings alphabetically using strcmp.
• Custom Struct Sorting: Sorting arrays of user-defined structures based on specific fields (e.g., sorting a list of students by their ID, name, or GPA).
• Multi-Criteria Sorting: Defining comparison functions that can sort based on multiple criteria, such as sorting a list of products first by category, then by price.
• Dynamic Sorting Logic: Allowing users to choose sorting criteria at runtime by passing different comparison functions.

Solution Approaches

The qsort function from has the following signature:

void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));

• base: A pointer to the first element of the array to be sorted.
• num: The number of elements in the array.
• size: The size (in bytes) of each element in the array.
• compar: A function pointer to a comparison function that takes two const void* arguments and returns an integer.

The compar function must return:

• A negative value if the first argument should come before the second.
• Zero if the two arguments are considered equal.
• A positive value if the first argument should come after the second.

Approach 1: Sorting an Array of Integers in Ascending and Descending Order

This approach demonstrates how to sort an array of integers using two different comparison functions.

One-line summary: Define comparison functions to sort integer arrays in both ascending and descending order.

// qsort Integers Ascending and Descending
#include <stdio.h>
#include <stdlib.h> // For qsort

// Comparison function for ascending order (a - b)
int compareAscending(const void *a, const void *b) {
    int int_a = *(const int *)a; // Cast void* to int* and dereference
    int int_b = *(const int *)b; // Cast void* to int* and dereference
    return int_a - int_b;
}

// Comparison function for descending order (b - a)
int compareDescending(const void *a, const void *b) {
    int int_a = *(const int *)a;
    int int_b = *(const int *)b;
    return int_b - int_a;
}

void printArray(const char *msg, int arr[], int n) {
    printf("%s: ", msg);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    // Step 1: Initialize an integer array
    int arr[] = {50, 20, 80, 10, 90, 30, 70, 40, 60};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Sort in ascending order
    qsort(arr, n, sizeof(int), compareAscending);
    printArray("Sorted (Ascending)", arr, n);

    // Step 3: Sort in descending order
    // Re-initialize array for clear demonstration
    int arr_desc[] = {50, 20, 80, 10, 90, 30, 70, 40, 60};
    qsort(arr_desc, n, sizeof(int), compareDescending);
    printArray("Sorted (Descending)", arr_desc, n);

    return 0;
}

Run

Sample Output:

Original array: 50 20 80 10 90 30 70 40 60 
Sorted (Ascending): 10 20 30 40 50 60 70 80 90 
Sorted (Descending): 90 80 70 60 50 40 30 20 10

Stepwise Explanation:

1. compareAscending Function: This function takes two const void* pointers. Inside, it casts them to const int* and then dereferences them to get the actual integer values. It returns int_a - int_b, which is negative if int_a is smaller, positive if int_a is larger, and zero if they are equal, achieving ascending order.
2. compareDescending Function: Similar to compareAscending, but returns int_b - int_a. This simple reversal of subtraction results in descending order.
3. main Function:

• An integer array arr is initialized.
• qsort is called with arr, its size, the size of each element (sizeof(int)), and the compareAscending function pointer.
• The array is printed.
• The process is repeated for descending order using compareDescending on a separate array for clarity.

Approach 2: Sorting an Array of Strings

This approach demonstrates sorting an array of C-style strings (character pointers).

One-line summary: Use strcmp within a comparison function to sort an array of strings alphabetically.

// qsort Strings Alphabetical
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <string.h> // For strcmp

// Comparison function for strings (alphabetical order)
int compareStrings(const void *a, const void *b) {
    // The elements of the array are char*, so a and b are pointers to char*
    const char *str_a = *(const char **)a; // Cast void* to char** and then dereference to get char*
    const char *str_b = *(const char **)b; // Cast void* to char** and then dereference to get char*
    return strcmp(str_a, str_b); // Use strcmp for string comparison
}

int main() {
    // Step 1: Initialize an array of strings (array of char pointers)
    char *fruits[] = {"banana", "apple", "grape", "orange", "kiwi", "pineapple"};
    int n = sizeof(fruits) / sizeof(fruits[0]);

    printf("Original strings:\\n");
    for (int i = 0; i < n; i++) {
        printf("- %s\\n", fruits[i]);
    }
    printf("\\n");

    // Step 2: Sort the array of strings
    qsort(fruits, n, sizeof(char *), compareStrings);

    printf("Sorted strings (alphabetical):\\n");
    for (int i = 0; i < n; i++) {
        printf("- %s\\n", fruits[i]);
    }
    printf("\\n");

    return 0;
}

Run

Sample Output:

Original strings:
- banana
- apple
- grape
- orange
- kiwi
- pineapple

Sorted strings (alphabetical):
- apple
- banana
- grape
- kiwi
- orange
- pineapple

Stepwise Explanation:

1. compareStrings Function:

• The array fruits holds char* elements. Therefore, qsort passes pointers to these char* elements, meaning a and b are void* pointers that actually point to char* variables.
• To get the actual char* (the string itself), a and b must first be cast to const char** (pointer to a char pointer) and then dereferenced.
• The strcmp function is used to compare the two strings. strcmp naturally returns a negative, zero, or positive value based on lexicographical order, perfectly fitting qsort's requirements.

1. main Function:

• An array of char* (strings) is initialized.
• qsort is called with fruits, its size, the size of each element (sizeof(char*)), and the compareStrings function pointer. Note the sizeof(char*) as the element size, not sizeof(char).

Approach 3: Sorting an Array of Custom Structures

This approach demonstrates how to sort an array of user-defined structures based on a specific member (e.g., an ID).

One-line summary: Create a comparison function to sort custom structs by one of their fields using type casting.

// qsort Structs by ID
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <string.h> // For strcpy

// Define a custom structure
typedef struct {
    int id;
    char name[50];
    float score;
} Student;

// Comparison function to sort Students by ID (ascending)
int compareStudentsByID(const void *a, const void *b) {
    // Cast void* to Student* and dereference to access members
    const Student *student_a = (const Student *)a;
    const Student *student_b = (const Student *)b;
    return student_a->id - student_b->id; // Compare IDs
}

// Comparison function to sort Students by Name (alphabetical)
int compareStudentsByName(const void *a, const void *b) {
    const Student *student_a = (const Student *)a;
    const Student *student_b = (const Student *)b;
    return strcmp(student_a->name, student_b->name); // Compare names using strcmp
}

void printStudents(const char *msg, Student students[], int n) {
    printf("%s:\\n", msg);
    for (int i = 0; i < n; i++) {
        printf("  ID: %d, Name: %s, Score: %.1f\\n", students[i].id, students[i].name, students[i].score);
    }
    printf("\\n");
}

int main() {
    // Step 1: Initialize an array of Student structures
    Student students[] = {
        {103, "Alice", 85.5},
        {101, "Bob", 92.0},
        {105, "Charlie", 78.0},
        {102, "David", 88.5},
        {104, "Eve", 95.0}
    };
    int n = sizeof(students) / sizeof(students[0]);

    printStudents("Original student list", students, n);

    // Step 2: Sort students by ID
    qsort(students, n, sizeof(Student), compareStudentsByID);
    printStudents("Sorted students by ID", students, n);

    // Step 3: Sort students by Name (using the same array)
    qsort(students, n, sizeof(Student), compareStudentsByName);
    printStudents("Sorted students by Name", students, n);

    return 0;
}

Run

Sample Output:

Original student list:
  ID: 103, Name: Alice, Score: 85.5
  ID: 101, Name: Bob, Score: 92.0
  ID: 105, Name: Charlie, Score: 78.0
  ID: 102, Name: David, Score: 88.5
  ID: 104, Name: Eve, Score: 95.0

Sorted students by ID:
  ID: 101, Name: Bob, Score: 92.0
  ID: 102, Name: David, Score: 88.5
  ID: 103, Name: Alice, Score: 85.5
  ID: 104, Name: Eve, Score: 95.0
  ID: 105, Name: Charlie, Score: 78.0

Sorted students by Name:
  ID: 103, Name: Alice, Score: 85.5
  ID: 101, Name: Bob, Score: 92.0
  ID: 105, Name: Charlie, Score: 78.0
  ID: 102, Name: David, Score: 88.5
  ID: 104, Name: Eve, Score: 95.0

Stepwise Explanation:

1. Student Structure: A Student structure is defined with id, name, and score members.
2. compareStudentsByID Function:

• a and b are void* pointers to Student structures. They are cast to const Student* to allow access to the struct's members using the -> operator.
• The function then compares the id members of the two students.

1. compareStudentsByName Function:

• Similar to compareStudentsByID, but it accesses the name members.
• strcmp is used to compare the names lexicographically.

1. main Function:

• An array of Student structs is initialized.
• qsort is called with the students array, its count, the size of each Student struct (sizeof(Student)), and the compareStudentsByID function pointer.
• The array is then sorted by name using compareStudentsByName.

Conclusion

The qsort function, combined with the power of function pointers, offers a highly flexible and efficient way to sort diverse data types in C. By providing custom comparison functions, developers can define precise sorting logic for primitive types, strings, and complex user-defined structures. This approach promotes code reusability and allows for dynamic sorting behaviors based on runtime requirements. Mastering qsort and function pointers is a crucial skill for writing robust and adaptable C applications.

Summary

• qsort is a standard library function for generic sorting.
• It requires a function pointer (compar) to define custom comparison logic.
• The compar function takes two const void* arguments, which must be cast to the appropriate data type before comparison.
• It returns a negative, zero, or positive integer to indicate the relative order of the elements.
• Function pointers enable sorting arrays of integers, strings, and custom structures based on various criteria.
• This mechanism is fundamental for writing flexible and reusable sorting routines in C.