In this article, we have explained how to use qsort that is Sorting using stdlib.h in C. We have presented the use-case using code examples.

Learn via Audio:

Pre-requisites

Functions in C, Arrays in C, Structures in C, Pointers in C, Function-pointers in C

stdlib is a C standard header file. So a typical C library provider would provide binaries of all the function definitions that the C standard specifies. One such function usage is discussed in this article. stdlib header comes with a function named qsort for, sorting elements. qsort stands for Quick-Sort and uses the same algorithm to sort elements. Quick sort algorithm itself is explained here.

Below is the qsort function's header as in stdlib.h:

void qsort (void *array, size_t count, size_t size, comparison_fn_t compare)

function takes an array (compile-time or dynamic array) and sorts the array elements in place. That means, array elements are modified and no extra array is created. In case of any such requirements, caller must take care of such things probably by duplicating the input array. Note the type of array that the function accepts is generic (in other words, any type is acceptable). So, the function can even work on user defined types (such as data-structures, unions).

Arrays in C are passed by reference (or pointer), so the calling function or the function definition will not be aware of number elements in the array and hence number of elements in the array shall also be passed as an argument. In the case of qsort function, this is nothing but count (second argument).

Any positive integer (integer as in maths) can be passed in it's place. The third argument refers to size of a single element in the passed array. Most of the sorting algorithms involve swapping or at least assigning an element to another element. As mentioned earlier, same function can be used on array of any type. But the function body is not aware of number of bytes that needs to be used while making an assignment operation.

One way to overcome this issue is by copying each byte of the element to required memory; may be by using memcpy function of C-standard. So third argument refers to number of bytes that need to copied in place of an assignment operation.

This is better understood with the below example:

consider this swapping operation of integer types

int temp, a, b; // where value of a & b has to be swapped
temp = a; a = b; b = temp;

The above can be done using functions in C as below, but caller shall pass address of the variable

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

The below code takes generic arguments and swaps them in place; but the code itself is not generic as it fits fine for integer types only. It demonstrates usage of typecasting generic pointer before dereferencing it.

void swap(void *a, void *b) {
    int temp;
    temp = *(int*)a;
    *(int*)a = *(int*)b;
    *(void*)b = temp;
}

The code can made generic if at least size of the elements that needs be swapped is known.

void swap(void *a, void *b, size_t size) {
    char temp;
    size_t i;
    // single iteration swaps one byte
    for (i = 0; i < size; ++i) {
        temp = *(char*)a;
        *(char*)a = *(char*)b;
        *(char*)b = temp;
    }
    // or the same operation can be achieved using memcpy is below
    // void *temp;
    // temp = malloc(size);
    // ... // error validation
    // memcpy(temp, a, size);
    // memcpy(a, b, size);
    // memcpy(b, temp,size);
    // free(temp);
}

Hope you realized importance of first three arguments. One more hurdle associated with the passed generic array is comparison operation inside qsort. Most of the sorting algorithms compare two elements and perform an action depending on the result of comparison.

We can compare predefined typed elements, but not user-defined typed elements. User defined types such as data structures would have many arguments and comparison of one field (or may be more fields) of two elements makes sense. But to do this, qsort function must be aware of type of element and field/s names that need to be involved in comparison. OR another way to overcome this issue by offloading job of comparison to caller itself. Fourth argument to qsort requires pointer to a function which takes two generic pointers and returns an integer.

Function pointers is well explained here. Type of the argument is a typedef for function pointer type which may look something like this:

typedef int (*comparison_fn_t)(const void *, const void *);

Caller must have a function which matches the above signature. The function shall not attempt to modify data pointed to by arguments. If the returned integer is greater than 0 than array is sorted in ascending order, if the value is negative, array elements are sorted in descending order, and no action is peformed if 0 is returned.

The below function can be passed as argument to qsort function for sorting an integer array in ascending order.

int cmp_asc_int(const void *a, const void *b) {
    const int *m, *n;
    m = (int *)a;
    n = (int *)b;
    return *m > *n;
}

or,

int cmp_asc_int(const void *a, const void *b) {
    return *(int*)a > *(int*)b;
}

Typecasting is necessary as received arguments are generic and can't be derefernced unless type is known.

Some points to remember when qsort function is used:

• Passed element shall be array that means, elements must be in contiguous in memory. Linked-lists or other sparsed data-structures can not be used with this api.
• There may be a requirement such that, only part of array needs to be sorted. In these cases pointer arithematic can be used but care must be taken on memory bounds to avoid memory corruptions.
• Compare function shall not modify elements passed to it.

Below example demonstrates usage of qsort to sort an integer array, to sort an user-defined type array.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// prints integer array elements seperated by 'seperator'
void print_int_array(const int a[], const unsigned int n, const char seperator) {
    unsigned int i;
    for (i = 0; i < n; ++i)
        printf("%d%c", a[i], seperator);
    puts("");
    fflush(stdout);
}

// function used for comparing two integer elements, used by qsort api
int cmp_asc_int(const void *a, const void *b) {
    return *(int*)a > *(int*)b;
}

typedef struct _student {
    unsigned int rollno;
    double percentage;
    char name[20];
} student_t;

// prints student array details in tabular format
// 'field_seperator' delimits each field of student structure
// 'record_seperator' character is displayed after each record is printed
// 'header' is a switch which prints header if non-zero value is passed
void print_student_array(const student_t a[], const unsigned int n, const char field_seperator, const char record_seperator, const int header) {
    unsigned int i;
    
    if (header) {
        // Display header with right-aligned field names
        printf("%7s%c%15s%c%7s%c", "Roll No", field_seperator, "Name", field_seperator, "Percentage", record_seperator);
    }

    for (i = 0; i < n; ++i) {
        printf("%7u%c%15s%c%7.2lf%c",
        a[i].rollno, field_seperator,
        a[i].name, field_seperator,
        a[i].percentage, record_seperator);
    }

    puts("");
    fflush(stdout);
}

// function used for comparing two string elements, used by qsort api
// passing this to qsort will sort students data in ascending order of
// their names
int cmp_asc_name(const void *s1, const void *s2) {
    return strcmp(
        ((student_t*)(s1))->name,
        ((student_t*)(s2))->name
        );
}

// function used for comparing two double elements, used by qsort api
// passing this to qsort will sort students data in ascending order of
// their percentages
int cmp_asc_percent(const void *s1, const void *s2) {
    return ((student_t*)(s1))->percentage > ((student_t*)(s2))->percentage;
}

int main()
{
    // int a[] = {98, 89, 12, 63, 88, 72, 8, 78, 58, 75}, i;
    
    student_t ece_14_18[] = {
        {
            rollno  : 1,
            percentage  : 80.06,
            name    : "Vishwa"
        },
        {
            rollno  : 2,
            percentage  : 90,
            name    : "Aditya"
        },
        {
            rollno  : 3,
            percentage  : 89,
            name    : "Rabindranath"
        },
        {
            rollno  : 4,
            percentage  : 96,
            name    : "Vallababhai"
        },
        {
            rollno  : 5,
            percentage  : 76,
            name    : "Vishweswarayya"
        },
    };

    print_int_array(a, sizeof(a) / sizeof(a[0]), ' ');
    // sorting integer array elements in ascending order
    qsort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]), cmp_asc_int);
    print_int_array(a, sizeof(a) / sizeof(a[0]), ' ');

    print_student_array(ece_14_18, sizeof(ece_14_18) / sizeof(ece_14_18[0]), '|', '\n', 1);
    // sorting student data in ascending order as per their name
    qsort(ece_14_18, sizeof(ece_14_18) / sizeof(ece_14_18[0]), sizeof(ece_14_18[0]), cmp_asc_name);
    print_student_array(ece_14_18, sizeof(ece_14_18) / sizeof(ece_14_18[0]), '|', '\n', 1);

    // sorting student data in ascending order as per their percentage
    qsort(ece_14_18, sizeof(ece_14_18) / sizeof(ece_14_18[0]), sizeof(ece_14_18[0]), cmp_asc_percent);
    print_student_array(ece_14_18, sizeof(ece_14_18) / sizeof(ece_14_18[0]), '|', '\n', 1);

    return 0;
}

Try it:

Understand the example code and alter it such that, student data is read from a file. Also, implement your own compare function such that, student data is sorted in ascending order of their names & if the names are same, consider roll numbers for making decision (ascending order). Write the output to another file (file may be stdout too ;P).

Time complexity:

• Worst case performance O(n^2)
• Best case performance O(nlogn) or even O(n) if partitioned in 3 ways
• Average complexity O(nlogn)

Space complexity:

• O(n) in worst case

Applications:

• qsort function can be used as a tool by programmers who don't care about partitioning algorithm but need best possible performance on their machine. Library for a machine is pre-compiled and so, it may use machine specific optimizations too.
  other applications are same as quick sort applications

With this article at OpenGenus, you must have the complete idea of qsort, Sorting using stdlib.h in C. Readers are encouraged to try different possibilities. Involve in the discussions or start a discussion on what you tried/failed at/succeeded at.