{"id":1269,"date":"2015-03-28T00:01:42","date_gmt":"2015-03-28T07:01:42","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1269"},"modified":"2015-04-04T12:40:07","modified_gmt":"2015-04-04T19:40:07","slug":"inside-the-quicksort","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1269","title":{"rendered":"Inside the Quicksort"},"content":{"rendered":"

The Internet is littered with plenty of good explanations of how the quicksort works. The definition at Wikipedia<\/a> graphically illustrates the process, which is commonly called “divide and conquer.” I’ve stolen the Wikipedia illustration and placed it into Figure 1.
\n
\n

Figure 1. A graphical illustration of the quicksort process. (Courtesy WikiMedia)<\/p><\/div><\/p>\n

As with a bubble sort, the quicksort eventually gets around to swapping items to order the array elements, but that swapping takes place only when necessary. Contrast that approach with the bubble sort, where all elements are exhaustively compared with each other. That’s why the bubble sort is inefficient.<\/p>\n

The quicksort creates a center point or pivot<\/em>. The algorithm examines values left and right of the pivot. Values are swapped when they’re less than or greater than the pivot point. This process takes place recursively to scan the entire range of values.<\/p>\n

Don’t worry if my explanation doesn’t clear the air for you. The bottom line with the quicksort is that a lot less swapping takes place than in a bubble sort.<\/p>\n

The following code contains my variation on the quicksort algorithm. Unlike other examples you’ll find on the Interwebs, I tried to make mine readable as opposed to clever.<\/p>\n

\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <time.h>\r\n\r\n#define SIZE 40\r\n\r\nvoid quicksort(int array[], int size);\r\n\r\nint main()\r\n{\r\n    int x,original[SIZE],sorted[SIZE];\r\n\r\n    srand((unsigned)time(NULL));\r\n    \/* populate arrays *\/<\/span>\r\n    for(x=0;x<SIZE;x++)\r\n        original[x] = sorted[x] = (rand() % 100)+1;\r\n\r\n    \/* do the quicksort *\/<\/span>\r\n    quicksort(sorted,SIZE);\r\n\r\n    \/* display the results *\/<\/span>\r\n    puts(\"Org\\tSorted\");\r\n    for(x=0;x<SIZE;x++)\r\n        printf(\"%3d\\t%3d\\n\",original[x],sorted[x]);\r\n\r\n    return(0);\r\n}\r\n\r\n\/*\r\n   Quicksort routine\r\n*\/<\/span>\r\nvoid quicksort(int array[], int size)\r\n{\r\n    int left,right,pivot,temp;\r\n\r\n    if(size < 2)            \/* stop recursion *\/<\/span>\r\n        return;\r\n    pivot = array[size\/2];  \/* set pivot point, value *\/<\/span>\r\n    right = size-1;\r\n    left = 0;\r\n    while(1)\r\n    {                       \/* scan for a swapping point *\/<\/span>\r\n        while(array[left] < pivot)\r\n            ++left;\r\n        while(pivot < array[right])\r\n            right--;\r\n        if(left >= right)   \/* stop if it's not found *\/<\/span>\r\n            break;\r\n                            \/* swap the values *\/<\/span>\r\n        temp = array[left];\r\n        array[left] = array[right];\r\n        array[right] = temp;\r\n        left++;             \/* keep looking *\/<\/span>\r\n        right--;\r\n    }\r\n                            \/* divide and search again *\/<\/span>\r\n    quicksort(array,left);\r\n    quicksort(array+left,size-left);\r\n}<\/pre>\n
In the code, two arrays are created, original[]<\/code> and sorted[]<\/code>. Both contain the same values, set at Line 16, but only the sorted[]<\/code> array is manipulated by using the quicksort()<\/em> function. That way you can see before and after in the program’s output.<\/p>\n
Here is sample output, which I truncated to fit on this webpage:<\/p>\n
Org\tSorted\r\n 29\t  1\r\n 97\t  2\r\n 96\t 11\r\n 26\t 17\r\n 11\t 17\r\n 85\t 19\r\n 66\t 22\r\n ...     ...\r\n 30\t 93\r\n 48\t 95\r\n 22\t 96\r\n 72\t 96\r\n 46\t 97\r\n  1\t 97<\/code><\/pre>\n
Of course, you can always use the qsort()<\/em> function, as demonstrated in last week’s Lesson<\/a>, which saves a dozen or so lines of code. By viewing the quicksort function in detail, however, you learn more about how it works. It might also help you understand and appreciate recursion.<\/p>\n
If you don’t understand recursion, starting by reading my series of Lessons: click here<\/a>.<\/p>\n
In next week’s Lesson<\/a>, I cover the process of sorting an array of strings by using the qsort()<\/em> function.<\/p>\n","protected":false},"excerpt":{"rendered":"
The qsort()<\/em> function does its magic thanks to 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-1269","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\/1269","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=1269"}],"version-history":[{"count":7,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1269\/revisions"}],"predecessor-version":[{"id":1318,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1269\/revisions\/1318"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1269"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1269"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1269"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}