230 Chapter 5 Programming Large 8-Bit Systems
optimization operation to skip over all variables that can be changed by the hardware portion of the system without knowledge of the program.
Sorting Programs
You might not expect that sorting routines would be important when programming microcontrollers, but there have been several instances in my experience where sorting of a list of data was needed in a microcontroller application. Therefore, let’s examine some sorting routines that can be used with a microcontroller and determine which of several popular approaches is best for use in a microcontroller program.
There are several sorting routines that are popular with program mers. The three most-used routines are named the entry sort, the Shell sort, and the quick sort. The entry sort is a routine that is thor oughly discredited because it is extremely slow when compared with the other routines. An entry sort orders the contents of an array in place. The first entry in the array is compared with the remaining entries and, if any array entry is smaller than the first, these values are swapped. This operation is then repeated for the second entry in the array followed by the third entry in the array until all entries in the array are compared with all others. When this sequence is com pleted, the array is sorted. If there are n entries in the array, the first scan involves n compares, the second involves n-1 compares, the third n-2 and so forth. Therefore, the total number of compares is
n+(n-1)+(n-2)+...1
The value of this sum is n*(n-1)/2. In other words, the entry sort requires on the order of n2 compares.
The Shell sort was discovered in 1959 by D. L. Shell. Like the entry sort, the Shell sort orders the contents of an array in place. The Shell sort splits the n-element array into two halves. The contents of these two halves are compared entry-by-entry and, if the value in the one half is larger than that in the other, the entries are swapped. These arrays are then split again, and the contents of the four arrays are scanned and ordered two at a time as above. Then the four arrays are split into eight arrays and the scan and ordering operation is repeated again. This operation of splitting the arrays and ordering the contents is repeated until there are n/2 arrays of 2 elements each. After this last scan and sort operation, the array is ordered.
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 log2 n is the number of times that an 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);
}
232 Chapter 5 Programming Large 8-Bit Systems
The outer loop in the preceding routine controls the way that the array is split. It first splits the array in half and then shrinks the arrays by halves until the sub arrays become zero in width. The second loop steps along the elements of the arrays, and the third loop compares the elements that are separated by split and swaps them when necessary.
The quick sort is:
/* quick_sort( int v[ ], int left, int right) : sort the array v into ascending order */
void quick_sort(int v[ ], int left, int right)
{
int i,pivot; if(right > left)
{
swap(v+left, v+(right+left)/2); /* chose the value at center to pivot on */
pivot = left;
for(i=left+1; i<=right; i++) if(v[i] < v[left])
swap(v+(++pivot), v+i); swap(v+left, v+pivot); /* put the partition
element in place*/ quick_sort(v,left, pivot-1); quick_sort(v,pivot+1,right);
}
}
The swap routine for both of these sorts is the same:
/* swap(int *, int *) : swap two integers in an array */
void swap(int *i, int *j)
{
int temp; temp = *i; *i=*j; *j=temp;
}
One of the nice things about both of these programs is that the swap operation is not built into the program. Therefore, you can swap values
Sorting Programs 233
as was done above, but also, you can swap pointers from an array of pointers to order a set of data that would be difficult to swap. For example, if you had a collection of words, you could use a srtcmp() routine to determine whether one word was lexically larger than the other and then write a swap routine that merely swapped the pointers to these words rather than swapping the words themselves. This approach to sorting a list of words is relatively simple. On the other hand, it would be extremely difficult—nearly impossible, in fact— to sort a list of words that are packed into memory.
The following program is used to test the performance of the above sort routines. The program simply makes an array of 11 entries and sorts the array by both the Shell sort and the quick sort. The result of this program is printed out below.
#include <stdio.h> main()
{
int v[]={81,99,23,808,3,77,18,27,128,360,550}; int i,k[11];
for (i=0;i<11;i++) k[i]=v[i]; shell_sort(k,11); for( i=0;i<11;i++)
printf (“%d “,k[i]); printf(“\n”); quick_sort(v, 0,11 -1); for( i=0; i<11; i++)
printf(“%d “,v[i]); printf(“\n”);
}
The original array is not printed out by the program, but the order of the array is seen in the above listing. The two sort programs sort the values correctly.
3 18 23 27 77 81 99 128 360 505 808
3 18 23 27 77 81 99 128 360 505 808
The quick sort routine is not the best example of recursive programming. Usually, the use of recursion results in a program that is significantly shorter than would be expected with conventional
234 Chapter 5 Programming Large 8-Bit Systems
linear programming. Here, the Shell sort requires fewer lines of C code and, as we will see, the Shell sort has a smaller assembly language program. You would not expect the linear program to be shorter in either C or assembly language. These two programs were compiled and the results analyzed.
The Shell sort requires 0x78 (120) bytes of code while the quick sort needs 0xaa (170) bytes of code. This amount of extra code would not be a serious cost if that were the end of the costs. However, each time a recursive routine calls itself it must establish an argument set that contains all of the variables to be passed to the function. When the quick_sort routine calls itself, it must pass three parameters. These parameters are usually passed in either the stack or in computer registers. When quick_sort returns control to the calling program, the stack pointer must be corrected. quick_sort will continue calling itself repeatedly while the value of the parameter right is greater than the value of the parameter left when the function is entered. Each time the function is called, the program will create a new stack frame which must be made available from RAM. Unfortunately, RAM is usually a more precious commodity than ROM to a microcontroller.
It is possible to get an idea about how much RAM is needed to do a quick sort. The stack frame consisting of six bytes—four bytes for parameters plus two bytes for the return address—must be created each time quick sort is entered. You can count the maximum number of times recursive routine calls itself. The maximum depth is the number of times the function is called before a normal return to the calling function is executed. The depth is found by incrementing a count each time the function is entered. Whenever control is passed back to the calling function through the normal return sequence at the end of the function, the depth will be evaluated to determine if it is the largest value seen so far, and then the depth will be returned to zero. The two listings below incorporate these modifications.
/* quick_sort( int v[ ], int left, int right) : sort the array v into ascending order */ void quick_sort(int v[ ], int left, int right)
{
int i,value;
extern int calls, depth, max_depth;
Sorting Programs 235
calls++; /* count the number of times called */ depth++;
if(right > left)
{
swap(v+left, v+(right+left)/2); /* chose the value at center to partition on */
value = left;
for(i=left+1; i<=right; i++) if(v[i] < v[left])
swap(v+(++value), v+i); swap(v+left, v+value); /* put the partition
element in place*/ quick_sort(v,left, value-1); quick_sort(v,value+1,right);
}
if(depth>max_depth) max_depth=depth; depth=0;
}
void swap ( int *, int *);
void quick_sort(int v[ ], int left, int right) ; #include <stdio.h>
int calls, depth, max_depth; main()
{
int v[11]={81,99,23,808,3,77,18,27,128,360,550}; int i;
quick_sort(v, 0,11 -1); for( i=0; i<11; i++)
printf(“%d “,v[i]); printf(“\n”);
printf(“calls=%d\nmax_depth=%d\n”,calls,max_depth);
}
Note that the global variables calls and depth are incremented each time quick_sort() is entered. When quick_sort() is exited through its normal return procedure at the end of the routine, depth is examined to determine if it is greater than max_depth .
236 Chapter 5 Programming Large 8-Bit Systems
If it is, max_depth is replaced by depth. depth is reset to zero prior to returning through the end of the quick_sort() routine. The result of this program is as follows:
3 18 23 27 77 81 99 128 360 550 808 calls=15
max_depth=4
To sort the above 11 element array, the program called quick_sort() 15 times and the maximum number of stack frames that were created at one time was four. Each stack frame consists of four bytes for data and two bytes for the return address. Therefore, at one time in the execution of this program, the sort routine required 24 bytes of stack space in addition to the memory area required to hold the array being sorted. This is distressing when you remember that the array is 22 bytes long!
Careful analysis of the program will show that the expected maximum number of stack frames for the quick sort is proportional to ln2n. Therefore, the stack frame performance will get better when the size of the array is larger. The main problem with the use of any recursive routine is that you do not know exactly the number of stack frames needed and therefore you must always analyze the maximum stack frame depth and allow that amount of stack for execution of the function.
The quick sort is faster than the Shell sort under most—but not all—circumstances. Let’s take the example of having a quick sort and a Shell sort compiled to run under the same host computer. If larger arrays are used to do the measurement and random arrays are used, we will find that the sort time for both quick sort and Shell sort depends on the array. The reason for this difference is the number of swap routines that must be executed during the sort operation. Therefore, there will be some arrays that the Shell sort will sort quicker that the quick sort. However, the quick sort is usually faster than the Shell sort.
The Shell sort is every bit as flexible as the quick sort and can be used to sort different types, character strings, and swap pointers rather than swap the objects being sorted. Therefore, in a microcontroller application where memory is always limited, you should use a Shell sort rather than a quick sort because the Shell sort has no funny memory requirements that will always occur with a recursive routine like the quick sort.