Page 246 - Programming Microcontrollers in C

Sorting Programs 231

There are n/2 compares completed each scan of the array.
However, the sort will be completed after the logarithm based-2 of n
times through the array, because log n is the number of times that an
2
array that contains n entries can be cut in half. Therefore, the time to
execute a Shell sort of an array of n items will be nearly proportional
to n*log (n). For even medium-sized arrays, this time is
2
significantly shorter than for the entry sort. For example, an array of
1000 entries requires time on the order of 1000000 to execute an
entry sort and 10000 to execute a Shell sort.
Another sort is the quick sort developed by C. A. R. Hoare in
1962. This sort is a recursive routine. It sorts an array in place. Assume
that the array runs from left to right and we want to sort the array in
ascending values from left to right. An array scan will place at least
one of the array values in the proper final array location. This entry
is called the pivot entry. As the scan is completed, all entries larger
than the pivot value are swapped to the right end of the array and
smaller values are placed in the left end of the array. When this
operation is completed, the two portions of the array—excluding the
pivot entry—are again quick sorted and the result of this recursive
operation is that the final result is sorted. This sorting operation also
requires time proportional to n*ln(n)/2.
The question now arises whether we should use a Shell sort or a
quick sort when writing code for a microcontroller. Let’s examine
these functions. The code for a Shell sort is as follows:

/* shell_sort(int v[ ], int i): sort the array v
of i things into ascending order */
void swap ( int *, int *);
void shell_sort(int v[ ], int i)
{
int split,m,n;
for( split = i/2 ; split > 0; split /=2 )
for( m = split ; m < i ; m++)
for ( n = m-split; n >=0 &&
v[n] > v[n+split]; n -= split)
swap(v+n,v+n+split);
}