Using the C Library’s qsort Function

I recently wrote an article on Bubble Sort, more as an academic exercise than a piece of practical and usable code. At the bottom of the post I suggested that the C library’s built-in qsort (Quicksort) function was the best option for sorting arrays in most situations.

However, there is more to using qsort than just throwing an array at a function: you need to provide your own comparator function, the implementation of which can be slightly fiddly if you are sorting anything other than primitive data types. In this article I’ll start off with a simple int-sorting example, and then go on to sort an array of structs, firstly by an int and then by a string.

My long list of ideas for future posts includes implementing various sorting algorithms so I won't go into how Quicksort works here. If you are interested take a look at the Wikipedia article Quicksort here. For the purposes of this project we'll just treat the qsort function as a "black box".

Coding

This is a short and simple project so I'll just keep all the code in one source file. Create a file called qsort.c somewhere convenient, and then type or paste the following. You can download the source code from the Downloads page if you prefer.

qsort.c (part 1)

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

// --------------------------------------------------------
// STRUCT author
// --------------------------------------------------------
typedef struct author
{
    int id;
    char name[64];
} author;

//--------------------------------------------------------
// FUNCTION PROTOTYPES
//--------------------------------------------------------
int compare_ints(const void* a, const void* b);
int compare_author_id(const void* a, const void* b);
int compare_author_name(const void* a, const void* b);

void output_ints(int* data, int size);
void output_authors(author* authors, int size);

void sort_integers();
void sort_authors();

//--------------------------------------------------------
// FUNCTION main
//--------------------------------------------------------
void main(void)
{
    puts("-------------------------\n| code-in-c.com - qsort |\n-------------------------\n");

    sort_integers();

    //sort_authors();
}

One of the #includes is stdlib.h, needed for the qsort function. We'll use the author struct in an array which we'll sort by both id and name. The first three functions prototyped here are the comparator functions needed by the qsort function. The next two functions simply output arrays of ints and authors. The last two functions are called by main, and will create, sort and output arrays of ints and authors respectively.

Sorting Integers

As you can see sort_authors is commented out in main, as to start with we will just implement sort_integers and its associated functions. Enter/paste the code for the three functions needed to sort integers into qsort.c.

qsort.c (part 2)

//--------------------------------------------------------
// FUNCTION sort_integers
//--------------------------------------------------------
void sort_integers()
{
    int data[16];
    srand(time(NULL));

    for(int i = 0; i < 16; i++)
    {
        data[i] = (rand() % 128);
    }

    puts("Unsorted");
    output_ints(data, 16);

    qsort(data, 16, sizeof(int), compare_ints);

    puts("Sorted");
    output_ints(data, 16);
}

//--------------------------------------------------------
// FUNCTION output_ints
//--------------------------------------------------------
void output_ints(int* data, int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%d\n", data[i]);
    }
}

//--------------------------------------------------------
// FUNCTION compare_ints
//--------------------------------------------------------
int compare_ints(const void* a, const void* b)
{
    if(*(int*)a < *(int*)b)
        return -1;
    else if(*(int*)a > *(int*)b)
        return 1;
    else
        return 0;
}

The sort_integers function creates an array of ints, populates it with random data, and outputs the data. (There is of course the possibility that the random numbers will already be in order. Sometimes writing software can be scary!)

Then we get down to business by calling qsort. This function takes four arguments:

  • The array to be sorted
  • The number of items in the array
  • The size of each item
  • A pointer to a comparator function taking two void pointer arguments, and returning an int

After calling qsort we simply output the data again in its sorted form.

I won't insult your intelligence by explaining how output_ints works, so let's move straight on to disentangling compare_ints. As I mentioned above it takes two void pointers, one to each of the values which need comparing. This makes qsort general-purpose in that it can sort anything by delegating the actual comparisons to custom functions. It does mean, however, that we have to do something with the pointers to get to the actual values we want to compare, exactly what we need to do with those pointers depends of course on what they are pointing to. The function then returns < 0 if the first argument is "less than" the second (using whatever logic is appropriate for your purposes), > 0 if the first is "more than" the second, and 0 if they are the same. The convention is to return -1, 1 or 0. (If for some reason you need to sort your data in descending order, just swap the return values.)

The core bits of the entire function are in the form

Getting an int from a void pointer

*(int*)a

which when you look at separately don't look so bad. In this particular case the pointer points to an int, so firstly we cast the void* to int*, and then dereference that pointer to give the actual value. These are then compared, and the appropriate value returned.

Compile the program with the following command in Terminal

Compile

gcc qsort.c -std=c11 -o qsort

and then run it with

Run

./qsort

You should see something like this.

Program Output

-------------------------
| code-in-c.com - qsort |
-------------------------

Unsorted
97
50
24
22
75
20
37
86
56
99
46
96
34
77
90
117
Sorted
20
22
24
34
37
46
50
56
75
77
86
90
96
97
99
117

That's about as simple as qsort gets, but now we will go on to sort something slightly more complicated, an array of structs. The principle is exactly the same, the big difference is that extracting the values we want to actually compare from the pointers is more involved.

Sorting Structs

Enter or paste the following into qsort.c, comment out sort_integers in main, and uncomment sort_authors.

qsort.c (part 3)

//--------------------------------------------------------
// FUNCTION sort_authors
//--------------------------------------------------------
void sort_authors()
{
    author authors[6];

    authors[0] = (author){.id = 7, .name = "Dickens, Charles"};
    authors[1] = (author){.id = 3, .name = "Stevenson, Robert Louis"};
    authors[2] = (author){.id = 9, .name = "Bronte, Emily"};
    authors[3] = (author){.id = 4, .name = "Gaskell, Elizabeth"};
    authors[4] = (author){.id = 1, .name = "Collins, Wilkie"};
    authors[5] = (author){.id = 8, .name = "Shelley, Mary"};

    puts("Unsorted");
    output_authors(authors, 6);

    qsort(authors, 6, sizeof(author), compare_author_id);
    puts("Sorted by id");
    output_authors(authors, 6);

    qsort(authors, 6, sizeof(author), compare_author_name);
    puts("Sorted by name");
    output_authors(authors, 6);
}

//--------------------------------------------------------
// FUNCTION output_authors
//--------------------------------------------------------
void output_authors(author* authors, int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("id: %d name: %s\n", authors[i].id, authors[i].name);
    }
}

//--------------------------------------------------------
// FUNCTION compare_author_id
//--------------------------------------------------------
int compare_author_id(const void* a, const void* b)
{
    if(((author*)a)->id < ((author*)b)->id)
        return -1;
    else if(((author*)a)->id > ((author*)b)->id)
        return 1;
    else
        return 0;
}

//--------------------------------------------------------
// FUNCTION compare_author_name
//--------------------------------------------------------
int compare_author_name(const void* a, const void* b)
{
    return strcmp(((author*)a)->name, ((author*)b)->name);
}

I'll gloss over the sort_authors and output_authors functions as they are essentially the same as the integer equivalents, except that we create, sort and output an array of authors rather than integers. Note though that we sort the array twice, firstly by id and secondly by name. The important functions here are compare_author_id and compare_author_name.

Let's look at compare_author_id first, and specifically getting at the ids from the pointers. The bits of code that do this are in the form

Getting an id from a void pointer

((author*)a)->id

Note that we need to cast the void pointer to an author pointer, the whole wrapped in brackets. If we did

Wrong!

(author*)a->id

we would be attempting to obtain the id property of a and then casting that to an author pointer, which of course is completely wrong and indeed meaningless. If we tried it the compiler would humiliate us with a suitable error message.

Now let's move on to compare_author_name which works slightly differently as we are now comparing strings. The C library has a built-in string comparison function strcmp (in string.h) which we will use, but we still need to get at the name properties to pass to strcmp. This is done in the same way as with id:

Getting a name from a void pointer

((author*)a)->name

The strcmp function returns the same < 0, 0, > 0 values that qsort expects so we can just return its return value as-is.

Build and run the program again and you should get

Program Output

-------------------------
| code-in-c.com - qsort |
-------------------------

Unsorted
id: 7 name: Dickens, Charles
id: 3 name: Stevenson, Robert Louis
id: 9 name: Bronte, Emily
id: 4 name: Gaskell, Elizabeth
id: 1 name: Collins, Wilkie
id: 8 name: Shelley, Mary
Sorted by id
id: 1 name: Collins, Wilkie
id: 3 name: Stevenson, Robert Louis
id: 4 name: Gaskell, Elizabeth
id: 7 name: Dickens, Charles
id: 8 name: Shelley, Mary
id: 9 name: Bronte, Emily
Sorted by name
id: 9 name: Bronte, Emily
id: 1 name: Collins, Wilkie
id: 7 name: Dickens, Charles
id: 4 name: Gaskell, Elizabeth
id: 8 name: Shelley, Mary
id: 3 name: Stevenson, Robert Louis

Of course you can create an array of anything, building up data structures of any complexity. It is therefore impossible to give examples of all possible comparator functions to be passed to qsort, but I hope this article is a good start. Please let me have any ideas, suggestions or questions in Comments below, and please follow Code in C on Twitter for news of future posts.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *