The Quicksort

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.

Leave a Reply