tpop(2.3): Libraries

2.3 Libraries

2011-03-10 Thu

2.3.1 Quicksort

• The standard libraries for C and C++ include sort functions that should be robust against adverse inputs, and tuned to run as fast as possible.
• Library routines are prepared to son any data type, but in return we must adapt to their interface.
• In C, the library function is named qsort, and we need to provide a comparison function to be called by qsort whenever it needs to compare two values. Since the values might be of any type, the comparison function is handed two void* pointers to the data items to be compared. The function casts the pointers to the proper type, extracts the data values, compares them, and returns the result (negative, zero or positive according to whether the first value is less than, equal to, or greater than the second).

Here's an implementation for sorting an array of strings, which is a common case. We define a function scmp to cast the arguments and call strcmp to do the comparison.

/* scmp: string compare of *p1 and *p2 */
int scmp (const void *p1, const void *p2)
{
    char *v1, *v2;

    v1 = *(char **)p1;
    v2 = *(char **)p2;
    return strcmp(v1, v2);
}

• We can't use strcmp directly as the comparison function because qsort passes the address of each entry in the array, &str[i] (of type char**), not str[i] (of type char*).

To sort elements str1 through str[N-1] of an array of strings, qsort must be called with the array, its length, the size of the items being sorted, and the comparison function:

char *str[N];

qsort(str, N, sizeof(str[0]), scmp);

Here's a similar function icmp for comparing integers:

/* icmp: integer compare of *p1 and *p2 */
int icmp(const void *p1, const void *p2)
{
        int v1, v2;

        v1 = *(int *) p1;
        v2 = *(int *) p2;
        if (v1 < v2)
                return -1;
        else if (v1 == v2)
                return 0;
        else
                return 1;
}

Again, the call to qsort requires the array, its length, the size of the items being sorted, and the comparison function:

int arr[N];

qsort(arr, N, sizeof(arr[0]), icmp);

2.3.2 Binary Search

2011-03-11 Fri
ANSI C also defines a binary search routine, bsearch. Like qsort, bsearch requires a pointer to a comparison function (often the same one used for qsort); it returns a pointer to the matching element or NULL if not found. Here is out HTML loopup routine, rewritten to use bsearch:

/* lookupV1: use bsearch to find name in tab, return index */
int lookupV1(char *name, Nameval tab[], int ntab)
{
        Nameval key, *np;

        key.name = name;
        key.value = 0; /* unused; anthing will do */
        np = (Nameval *)bsearch(&key, tab, ntab, sizeof(tab[0]), nvcmp);

        if (np == NULL)
                return -1;
        else
                return np-tab;
}

As with qsort, the comparison routine receives the address of the items to be compared, so the key must have that type; in this example, we need to construct a fake Nameeval entry that is passed to the comparison routine itself is a function nvcmp that compares two Nameval items by calling strcmp on their string components, ignoring their values:

/* nvcmp: compare two Nameval names */
int nvcmp(const void *va, const void *vb)
{
        const Nameval *a, *b;
        a = (Nameval *)va;
        b = (Nameval *)vb;
        return strcmp(a->name, b->name);
}

This is analogous to scmp but differs because the strings are stored as members of a structure.

It's a good idea to use bsearch instead of writing your own. Over the years, binary search has proven suprisingly hard for programmers to get right.

The standard C++ library has a generic algorithm called sort that guarantees O(nlog n) behavior.

int arr[N];
sort(arr, arr+N);

The C++ library also has generic binary search routines, with similar notational advantages.