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 as a zip or clone/download the Github repository if you prefer.
Source Code Links
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("-----------------"); puts("| codedrome.com |"); puts("| qsort |"); puts("-----------------\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
----------------- | codedrome.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
----------------- | codedrome.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.