Computers excel at searching and sorting. That, and they can occasionally screw up a phone bill.
For 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.
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()
The qsort() function is defined in the stdlib.h
header file. It swallows four arguments:
*base
The address of the array to be sorted
nel
The number of elements in the array
width
The size of each element, generally obtained by using the sizeof operator
compar
The name of a function that determines how the array elements are compared
Possibly the weirdest argument is compar
, 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.)
The compar
function, which is traditionally named compare() has a very specific format. Here’s what’s most often used:
int compare(const void *a, const void *b) { return( *(int *)a - *(int *)b); }
You can change the function’s insides, and the variables used in the function (a
and b
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.
Below is updated code from last week’s Lesson. This code uses the qsort() function instead of a bubble sort.
#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 100000 int compare(const void *a, const void *b); int main() { int qarray[SIZE]; int x; srand((unsigned)time(NULL)); /* populate array */ for(x=0;x<SIZE;x++) { qarray[x] = rand(); qarray[x] = (qarray[x] % 100)+1; } printf("%d element array created.\n",SIZE); /* quicksort */ printf("Sorting . . . "); qsort(qarray,SIZE,sizeof(int),compare); puts("done!"); return(0); } int compare(const void *a, const void *b) { return( *(int *)a - *(int *)b); }
Here is the program’s output when monitored by the time command:
100000 element array created.
Sorting . . . done!
real 0m0.026s
user 0m0.007s
sys 0m0.001s
For reference, here is the output from last week’s code, which used a bubble sort:
100000 element array created.
Sorting . . . Done!
real 0m9.910s
user 0m9.899s
sys 0m0.011s
As you can see, the qsort() is just insanely more efficient at its job than the bubble sort; it’s more than 9 seconds faster on my machine.
If you want to reverse the sort, change the variable order in the compare() function, swapping b
for a
in the comparison:
int compare(const void *a, const void *b) { return( *(int *)b - *(int *)a); }
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.
Next week I’ll cover how the quicksort works. It’s really rather ingenious.