{"id":1293,"date":"2015-04-11T00:01:57","date_gmt":"2015-04-11T07:01:57","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1293"},"modified":"2015-04-04T13:00:28","modified_gmt":"2015-04-04T20:00:28","slug":"quicksorting-strings-pointer-edition","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1293","title":{"rendered":"Quicksorting Strings, Pointer Edition"},"content":{"rendered":"

I’ll confess that when I use a quicksort to sort and array of strings, I don’t use the C Library’s qsort()<\/em> function. No, I write my own. The problem is that when sorting an array of strings, the qsort()<\/em> function’s compar<\/em> argument is a pain in the butt to craft properly.
\n
\nAn array of strings is an array of pointers. Because an array itself is a pointer, the end result is a pointer to a pointer, or the ugly **<\/code> thing, which I’ve written about elsewhere on this site.<\/p>\n

The beauty of the pointer array is that the strings themselves aren’t messed with; only the pointers are sorted (based on the strings). For the qsort()<\/em> function, the problem is how to translate an array of pointers into something that the compare()<\/em> function swallows in an obedient manner.<\/p>\n

As a review, here is the pattern normally used in the compare()<\/em> function:<\/p>\n

int compare(const void *a, const void *b)\r\n{\r\n    return( *(type<\/em> *)a - *(type<\/em> *)b);\r\n}<\/code><\/pre>\n
The function’s two arguments never change. They are const void<\/em> types. const<\/em> means that the variable’s value cannot change; it’s constant. void<\/em> identifies the variables as pointers of a non-specific type. The variable is typecast properly within the function, typically within the return<\/em> statement, as shown above.<\/p>\n
With a pointer-to-a-pointer variable, you would think you could get away with something like the following to compare two strings:<\/p>\n
    return( strcmp((char **)a,(char **)b) );<\/code><\/pre>\n
Alas, no: That doesn’t work. It’s essentially a stab in the dark — a good stab, close to the solution, but wrong.<\/p>\n
The problem is the const<\/em> keyword. The variables must still be treated as constants, so that keyword must be part of the solution. The typecast for an array of strings is correctly (char **)<\/code>, but that still doesn’t handle the fact that the strcmp()<\/em> function needs pointers, not pointer-pointers. So another asterisk is required to make that function happy.<\/p>\n
Yes, 10,000 monkeys sitting at keyboards with an abundance of asterisk keys would eventually divine a solution. Rather than wait that long, behold my solution, using similar code as presented in last week’s Lesson<\/a>, but using pointer notation to create the array of strings:<\/p>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <string.h>\r\n\r\n#define C 15\r\n\r\nint compare(const void *a, const void *b);\r\n\r\nint main()\r\n{\r\n    char *crew[] = {\r\n        \"Thorin\",   \"Fili\", \"Kili\",\r\n        \"Bilbo\",    \"Dori\", \"Balin\",\r\n        \"Dwalin\",   \"Ori\",  \"Gloin\",\r\n        \"Bifur\",    \"Nori\", \"Bofur\",\r\n        \"Bombur\",   \"Oin\",  \"Gnadalf\"\r\n    };\r\n    int x;\r\n\r\n    \/* print original strings *\/<\/span>\r\n    printf(\"Original: \");\r\n    for(x=0;x<C;x++)\r\n        printf(\"%s \",crew[x]);\r\n    putchar('\\n');\r\n\r\n    \/* quicksort the list *\/<\/span>\r\n    qsort(crew,C,sizeof(char *),compare);\r\n\r\n    \/* print sorted strings *\/<\/span>\r\n    printf(\"  Sorted: \");\r\n    for(x=0;x<C;x++)\r\n        printf(\"%s \",crew[x]);\r\n    putchar('\\n');\r\n\r\n    return(0);\r\n}\r\n\r\nint compare(const void *a, const void *b)\r\n{\r\n    const char **pa,**pb;\r\n\r\n    pa = (const char **)a;\r\n    pb = (const char **)b;\r\n    return( strcmp(*pa,*pb) );\r\n}<\/pre>\n
To make the code in the compare()<\/em> function more readable, I use two pointer-pointer variables, pa<\/code> and pb<\/code>. These are assigned the values of the two pointers passed to the function, a<\/code> and b<\/code>, both of which must be typecast to the **<\/code> thing; an array of pointers. (That’s what’s being sorted.)<\/p>\n
Once pa<\/code> and pb<\/code> are assigned, they can then be used in the strcmp()<\/em> function, nestled in the return<\/em> statement. The pointer operator *<\/code> is required inside the strcmp()<\/em> function because array elements are being sorted, not the entire array, which is how the compiler sees a **<\/code> variable.<\/p>\n
Yes, that’s confusing! Don’t feel bad if you’re intimidated by the entire thing.<\/p>\n
Of course, my solution above is written for readability. You can reduce the compare()<\/em> function to a single return statement, if you’re really crazy:<\/p>\n
    return( strcmp( *((const char **)a), *((const char **)b)) );<\/code><\/pre>\n
I don’t fault anyone for not coming up with this solution on their own. It is not easy! But that’s the way it’s done. Even advanced C programmers write down stuff like this so that they don’t have to re-think the solution later.<\/p>\n","protected":false},"excerpt":{"rendered":"
It’s your old nemesis, the **<\/code> thing. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-1293","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1293"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1293\/revisions"}],"predecessor-version":[{"id":1321,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1293\/revisions\/1321"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}