Page 94 - Programming Microcontrollers in C

Pointers 79

the contents of an array, so it might be possible to simply modify the
shell sort to do this job.
First, a comparison is needed that will determine if the lexical value
of a one word is smaller, equal, or larger than that of another word. Such
a compare routine was outlined above. Second, a swap routine that will
swap the words that are in the wrong order. Here is a case where an array
of pointers can be quite useful. Assume that the program that reads in the
data will put each word into a separate memory location and keep an
array of pointers to the beginning of each word rather than just the array
of the words themselves. Then in the shell sort, when a swap is required,
rather than swapping the words, swap the pointers in the array. Swap
routines that swap pointers in the array are very easy to implement. On
the other hand, swap routines to swap two strings in memory are diffi­
cult and slow. Therefore, we can create a sort routine that is much more
efficient if we use an array of pointers rather than an array of strings.

/* shell_sort(): sort the contents of the array
char* v[] into ascending order */

#include <string.h>
void shell_sort(char* v[], int n)
{
int gap, i, j;
char* temp;
for( gap = n/2; gap > 0; gap /= 2)
for( i=gap; i < n; i++)
for( j=i-gap; j>=0 &&
strcmp(v[j],v[j+gap]); j -= gap)
{
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = v[j];
}
}

Here the strcmp() routine is used to determine if a swap is
needed. strcmp() is identified in the header file string.h. When
needed, the contents of the array of pointers to the beginning of the
words is swapped rather than swapping the words themselves.