{"id":1258,"date":"2015-03-21T00:01:09","date_gmt":"2015-03-21T07:01:09","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1258"},"modified":"2015-03-28T07:20:54","modified_gmt":"2015-03-28T14:20:54","slug":"the-quicksort","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1258","title":{"rendered":"The Quicksort"},"content":{"rendered":"

Computers excel at searching and sorting. That, and they can occasionally screw up a phone bill.
\n
\nFor years, programmers have tried to improve upon the basic search and sort operations. Algorithms exist to search and sort faster. One of the more popular sorting algorithms is the quick sort. It’s so popular, the space between the words was evicted, so it’s known as quicksort<\/em>.<\/p>\n

I’ll demonstrated how the quicksort works in detail in next week’s Lesson. The details are interesting, but not vital to know because a quicksort function is available in the standard C library: qsort()<\/em><\/p>\n

The qsort()<\/em> function is defined in the stdlib.h<\/code> header file. It swallows four arguments:<\/p>\n

*base<\/code> The address of the array to be sorted<\/p>\n

nel<\/code> The number of elements in the array<\/p>\n

width<\/code> The size of each element, generally obtained by using the sizeof<\/em> operator<\/p>\n

compar<\/code> The name of a function that determines how the array elements are compared<\/p>\n

Possibly the weirdest argument is compar<\/code>, which is simply the name of another function elsewhere the code. (Internally, it’s the address of that function, which is a topic I’ll save for a future Lesson.)<\/p>\n

The compar<\/code> function, which is traditionally named compare()<\/em> has a very specific format. Here’s what’s most often used:<\/p>\n

\r\nint compare(const void *a, const void *b)\r\n{\r\n    return( *(int *)a - *(int *)b);\r\n}<\/pre>\n
You can change the function’s insides, and the variables used in the function (a<\/code> and b<\/code> above) must match the array’s variable type. Otherwise, the return value is less than zero, zero, or greater than zero depending on how the two values compare. Using the minus operator, as shown above, is how just about everyone does the comparison for an array of values sorted least to greatest.<\/p>\n
Below is updated code from last week’s Lesson<\/a>. This code uses the qsort()<\/em> function instead of a bubble sort.<\/p>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <time.h>\r\n\r\n#define SIZE 100000\r\n\r\nint compare(const void *a, const void *b);\r\n\r\nint main()\r\n{\r\n    int qarray[SIZE];\r\n    int x;\r\n\r\n    srand((unsigned)time(NULL));\r\n    \/* populate array *\/<\/span>\r\n    for(x=0;x<SIZE;x++)\r\n    {\r\n        qarray[x] = rand();\r\n        qarray[x] = (qarray[x] % 100)+1;\r\n    }\r\n    printf(\"%d element array created.\\n\",SIZE);\r\n\r\n    \/* quicksort *\/<\/span>\r\n    printf(\"Sorting . . . \");\r\n    qsort(qarray,SIZE,sizeof(int),compare);\r\n    puts(\"done!\");\r\n\r\n    return(0);\r\n}\r\n\r\nint compare(const void *a, const void *b)\r\n{\r\n    return( *(int *)a - *(int *)b);\r\n}<\/pre>\n
Here is the program’s output when monitored by the time<\/em> command:<\/p>\n
100000 element array created.\r\nSorting . . . done!\r\n\r\nreal\t0m0.026s\r\nuser\t0m0.007s\r\nsys\t0m0.001s<\/code><\/pre>\n
For reference, here is the output from last week’s code, which used a bubble sort:<\/p>\n
100000 element array created.\r\nSorting . . . Done!\r\n\r\nreal\t0m9.910s\r\nuser\t0m9.899s\r\nsys\t0m0.011s<\/code><\/pre>\n
As you can see, the qsort()<\/em> is just insanely more efficient at its job than the bubble sort; it’s more than 9 seconds faster on my machine.<\/p>\n
If you want to reverse the sort, change the variable order in the compare()<\/em> function, swapping b<\/code> for a<\/code> in the comparison:<\/p>\n
\r\nint compare(const void *a, const void *b)\r\n{\r\n    return( *(int *)b - *(int *)a);\r\n}<\/pre>\n
Of course, you have to modify the code to display all 100,000 values to prove that the sort is reversed. Trust me: It works.<\/p>\n
Next week<\/a> I’ll cover how the quicksort works. It’s really rather ingenious.<\/p>\n","protected":false},"excerpt":{"rendered":"
Yes, it’s much faster than a bubble sort. 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-1258","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\/1258","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=1258"}],"version-history":[{"count":9,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1258\/revisions"}],"predecessor-version":[{"id":1307,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1258\/revisions\/1307"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}