Page 90 - Programming Microcontrollers in C

Pointers 75

discovered by D. L. Shell. The Shell sort allows the array to be
sorted with n times the logarithm base two of n. This difference
can be substantial. For example, if the array contains 1000 ele­
ments, the bubble sort will require on the order of 1,000,000
compares and swaps while the Shell sort will need only 10,000.
Therefore, the bubble sort should not be used to sort large arrays.
Another sort technique that is used was discovered by C. A. R.
Hoare. This technique is called the quick sort. It uses a recursive
approach to accomplish the sort, and it also requires n log base 2 of
n compares and swaps. The shell sort and the quick sort usually
require about the same time to accomplish the sort. We will dem­
onstrate a shell sort now.
The code for a shell sort follows. Note that extensive use of
pointers is used in this version of the shell sort.

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

void shell_sort(int* v, int n)
{
int gap, i, j, temp;

for( gap = n/2; gap > 0; gap /= 2)
for( i=gap; i < n; i++)
for(j=i-gap;j>=0&&*(v+j)>*(v+j+gap);
j -= gap)
{
temp = *(v+j);
*(v+j) = *(v+j+gap);
*(v+j+gap) = *(v+j);
}
}
The shell sort receives as arguments a pointer to an array of inte­
gers and an integer n which is the length of the array.
This sort works by successively dividing the array into subarrays.
The first operation divides the whole array into two parts; the second
divides each of the two subarrays into two new subarrays, for a total
of four arrays; and so forth.