Page 249 - Programming Microcontrollers in C

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;