{"id":1287,"date":"2015-04-04T00:01:20","date_gmt":"2015-04-04T07:01:20","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1287"},"modified":"2019-01-03T19:47:15","modified_gmt":"2019-01-04T03:47:15","slug":"quicksorting-strings","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1287","title":{"rendered":"Quicksorting Strings"},"content":{"rendered":"

The quicksort deftly handles vast quantities of values. It can also sort strings, but that’s where things can get weird.
\n
\nIf you’re coding your own quicksort function, then you can code a string comparison routine within that function. When you use the C Library’s qsort()<\/em> function, however, the issue becomes how to craft the proper compare()<\/em> function.<\/p>\n

The following code creates an array of 15 strings. I’ve used array notation, because it’s a big easier to follow when using the qsort()<\/em> function. The constant C<\/code> holds the number of array elements:<\/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[C][8] = {\r\n        \"Thorin\",   \"Fili\", \"Kili\",\r\n        \"Bilbo\",    \"Dori\", \"Balin\",\r\n        \"Dwalin\",   \"Ori\",  \"Gloin\",\r\n        \"Bifur\",    \"Nori\", \"Bofur\",\r\n        \"Bombur\",   \"Oin\",  \"Gandalf\"\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,8,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    return( strcmp((char *)a,(char *)b) );\r\n}<\/pre>\n
The qsort()<\/em> function at Line 27 uses 8 as the size of each item to be sorted, which is the second element in the two-dimensional string array (Line 11). The compare()<\/em> function uses the strcmp()<\/em> function to compare both strings. Coincidentally, the strcmp()<\/em> function returns values identical to what must be returned for the compare()<\/em> function: less than zero, zero, or greater than zero, depending on how the strings compare.<\/p>\n
Here’s sample output:<\/p>\n
Original: Thorin Fili Kili Bilbo Dori Balin Dwalin Ori Gloin Bifur Nori Bofur Bombur Oin Gandalf \r\n  Sorted: Balin Bifur Bilbo Bofur Bombur Dori Dwalin Fili Gandalf Gloin Kili Nori Oin Ori Thorin <\/code><\/pre>\n
While this code works, the drawback is that not every array of strings is crafted by using a two-dimensional array. Most string arrays are pointer arrays, which use the dratted double asterisk, **<\/code>. I’ll cover how to quicksort that monster in next week’s Lesson<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
A lethal mix of pointers and recursion. 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-1287","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\/1287","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=1287"}],"version-history":[{"count":8,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1287\/revisions"}],"predecessor-version":[{"id":3453,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1287\/revisions\/3453"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}